53. Maximum Subarray

Problem from leetcode 53. Maximum Subarray

---

这是一道典型的 动态规划 dynamic programming 问题，时间复杂度是O(n)。也可以用divide and conquer来做，时间复杂度是O(nlogn)。

---

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        //dp[i] store the maximum subarray for range [0, i]
        // and nums[i] is included
        vector<int> dp(size, 0);
        dp[0] = nums[0];
        for(int i = 1; i < size; ++i) 
            if(dp[i-1] > 0)
                dp[i] = nums[i]+dp[i-1];
            else
                dp[i] = nums[i];
        
        //we don't know where is the end index of the maximum subarray
        //but it must be either 0 or 1 or 2 or 3 or 4....
        int maximum = dp[0];
        for(int i = 1; i < size; ++i)
            maximum = maximum<dp[i]?dp[i]:maximum;
        return maximum;
    }
};

当然上面的代码我们可以用滚动数组来降低空间复杂度：

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

Java:

public class Solution {
    public int maxSubArray(int[] nums) {
        int length = nums.length;
        int maximum = nums[0];
        int[] dp = new int[length];
        dp[0] = nums[0];
        for(int i = 1; i < length; ++i) 
        { 
            dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
            maximum = maximum<dp[i]?dp[i]:maximum;
        }
        return maximum;
    }
}

Python:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        maximum, dp = nums[0], [0]*length
        dp[0] = nums[0]
        for i in range(1, length):
            dp[i] = nums[i] if dp[i-1] < 0 else dp[i-1]+nums[i] 
            maximum = dp[i] if dp[i]>maximum else maximum
        return maximum