leetcode-53-Maximum-Subarray

发表于   |  

描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

分析

求最大子序列和，非常经典的动态规划问题。首先，如果这个数组只有1个值，显而易见结果就是这个唯一的值 s[0]，如果是2个值，那么我们将考虑第2个值是否对结果有利，如果第1个值和第2个值相加是大于第2个值的，那么整个数组的最大值就是 s[0]+s[1]，否则就是 s[1]，以此类推，如果数组里的第 n 个值对之前的结果是有利的，那么我们把它加进来，从 1 到 n 这个数组的最大子序列和就是 f(n-1) + s[n]，否则，1 到 n 这个数组的最大子序列和是 s[n]。依靠这些条件我们可以得到状态转移方程：
$$
f(i) =
\begin{cases}
s[0], & (i=0) \\
max(f(i-1)+s[i], s[i]), & (1 \le i \le n)
\end{cases}
$$

$$
result = max(f(i)), 0 \le i \le n
$$

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = nums[0]
        f = 0
        for i in range(len(nums)):
            f = max(f+nums[i], nums[i])
            result = max(result, f)
            
        return result

解决方案2(C++)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN, f = 0;
        for (int i=0; i < nums.size(); i++) {
            f = max(f+nums[i], nums[i]);
            result = max(result, f);
        }
        return result;
    }
};

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxSubArray(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }   
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    result := dp[0]

    for i := 1; i < len(nums); i++ {
        if nums[i] + dp[i-1] > nums[i] {
            dp[i] = nums[i] + dp[i-1]
        } else {
            dp[i] = nums[i]
        }
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}

相关问题

题目来源