题目描述

给一个array，找一个连续的子数组，它的sum是最大的，返回sum值。

我的解法——求前n项和+DP

遍历两遍数组
n的复杂度。
结果：beat 37.26%

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        length = len(nums)
        if(length == 1):
            return nums[0]
        
        for i in range(1,length):
            nums[i] += nums[i - 1]
            
        smallest = 0
        res = nums[0]
        for i in range(length):
            last = nums[i]  # 注意这里，后面的smallest要和被修改之前的nums[i]进行比较！！！！
            nums[i] = nums[i] - smallest
            if(last < smallest):
                smallest = last
            if(nums[i] > res):  #保存结果
                res = nums[i]

        return res

其他解法——DP

令sum[i]表示从i开始的最大子串和，则有递推公式：sum[i] = max{A[i], A[i] + sum[i+1]}
n的时间复杂度

int maxSubArray(int A[], int n) {
  int sum = A[n - 1];
  int maxSum = sum;

  for (int i = n - 2; i >= 0; i--) {
    sum = max(A[i], sum + A[i]);
    maxSum = max(maxSum, sum);
  }

  return maxSum;
}