How to Solve LeetCode 53: Maximum Subarray Sum with Dynamic Programming

Problem Statement

Given an integer array, find the contiguous sub‑array with the largest sum.

Dynamic‑Programming Idea

Define dp[i] as the maximum sum of a sub‑array that ends at index i. The overall answer is the maximum value among all dp[i].

Recurrence

For each i>0, dp[i] = max(dp[i‑1] + nums[i], nums[i]). This compares extending the previous best sub‑array with starting a new sub‑array at i.

Base Case

Since a sub‑array must contain at least one element, dp[i] is initialized to nums[i] for every i.

Final Result

After filling dp, iterate through it to obtain the greatest value, which is the required maximum sub‑array sum.

Complete Go Implementation

func maxSubArray(nums []int) int {
    // dp[i] stores the maximum sum of a sub‑array ending at i
    dp := make([]int, len(nums))

    // base case: each dp[i] starts as the element itself
    for k, _ := range dp {
        dp[k] = nums[k]
    }

    // compute dp for each element as the ending element
    for i := 0; i < len(nums); i++ {
        if i-1 >= 0 {
            dp[i] = max(dp[i], dp[i-1]+nums[i])
        }
    }

    result := math.MinInt
    // find the global maximum among all dp[i]
    for _, v := range dp {
        result = max(result, v)
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}