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.

题解：

输入一个数组，求数组的连续子数组中，最大的一段的和；
原问题：n个数的数组（nums）的最大子段和；
子问题：
一个数的数组的最大子段和：dp[0] = nums[0]；
两个数的数组的最大子段和：两种情况，加上第一个数(dp[0] + nums[1])或不加上第一个数(nums[1])：dp[1] = max(dp[0] + nums[1], nums[1])；其实也就相当于是以第二个数作为子段结尾的情况下的最优解；然后再取max(dp[0], dp[1])；
确认状态：
n个数的数组的最大子段和：
以nums[n-1]结尾的最大子段和前n-1个子段最大和比较，取最大值；
动态规划状态转移方程：
以第n个数结尾的最大子段和：dp[n-1] = (dp[n-2] + nums[n-1], nums[n-1])
边界状态：dp[0] = nums[0]；
最后输出：max(dp[0]，dp[1]，.....dp[n-1])

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        vector<int> dp(nums.size() + 3, 0);
        if (nums.size() == 0) {
            return 0;
        }
        dp[0] = nums[0];
        int max_dp = dp[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (max_dp < dp[i]) {
                max_dp = dp[i];
            }
        }
        return max_dp;
    }
};

int main() {
    vector<int> nums;
    nums.push_back(-2);
    nums.push_back(1);
    nums.push_back(-3);
    nums.push_back(4);
    nums.push_back(-1);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(-5);
    nums.push_back(4);
    Solution s;
    printf("最大子段和：%d", s.maxSubArray(nums));
    return 0;
}

结果

最大子段和：6

My Solution 1(Python)

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum, result = 0, 0
        for i in range(len(nums)):
            sum += nums[i]
            if sum < 0:
                sum = 0
            else:
                result = max(sum, result)
        if result == 0:
            return max(nums)
        return result

My Solution 2(Python)

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = []
        if len(nums) == 0:
            return []
        dp.append(nums[0])
        max_dp = dp[-1]
        for i in range(1, len(nums)):
            dp.append(max(dp[i-1] + nums[i], nums[i]))
            if max_dp < dp[-1]:
                max_dp = dp[-1]
        return max_dp

Reference (转)

Python:

class Solution(object):
    def maxSubArray(self, nums):
        for i in xrange(1,len(nums)):nums[i]=max(nums[i], nums[i]+nums[i-1])
        return max(nums)

Java:

class Solution {
public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        
        return max;
}
}