53. Maximum Subarray

53. Maximum Subarray

1 题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

2 解题 && 思路

本题可以使用动态规划的方式来解决。设dp[i]是数组第i处的最大值，则dp[i]的递推表达式是:

1. 如果dp[i-1]>0，则dp[i] = dp[i-1] + nums[i]
2. 如果dp[i] < 0 ，则dp[i] = nums[i]

3. 实现

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