Maximum Subarray

Question

• leetcode: Maximum Subarray | LeetCode OJ
• lintcode: (41) Maximum Subarray

Given an array of integers,
find a contiguous subarray which has the largest sum.

Example
Given the array [−2,2,−3,4,−1,2,1,−5,3],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note
The subarray should contain at least one number.

Challenge
Can you do it in time complexity O(n)?

题解1 - 贪心

求最大子数组和，即求区间和的最大值，不同子区间共有约 $$n^2$$ 中可能，遍历虽然可解，但是时间复杂度颇高。

这里首先介绍一种巧妙的贪心算法，用sum表示当前子数组和，maxSum表示求得的最大子数组和。当sum <= 0时，累加数组中的元素只会使得到的和更小，故此时应将此部分和丢弃，使用此时遍历到的数组元素替代。需要注意的是由于有maxSum更新sum, 故直接丢弃小于0的sum并不会对最终结果有影响。即不会漏掉前面的和比后面的元素大的情况。

• reference

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxSubArray(self, A):
        ThisSum = 0
        MaxSum = -10000

        for i in range( 0, len(A) ):
            if ThisSum < 0:
                ThisSum = 0
            ThisSum = ThisSum + A[ i ]
            MaxSum = max( ThisSum, MaxSum )

        return MaxSum