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.

Solution

(1) Greedy

sum is the running number which keep running for the sum

the max should be currnt sum running - min sum running.

(2) Prefix

(3) DP

全局局部， 划分型动态规划

class Solution:
    """
    @param nums: A list of integers
    @return: An integer denote the sum of maximum subarray
    """
    def maxSubArray(self, nums):
        # write your code here
        maxSum = sys.maxsize * -1
        sum = 0

        for x in nums:
            sum += x
            maxSum = max(maxSum, sum)
            sum = max(sum, 0)

        return maxSum

DP

class Solution:
    """
    @param nums: A list of integers
    @return: An integer denote the sum of maximum subarray
    """
    def maxSubArray(self, nums):
        # write your code here
        n = len(nums)

        if n <= 0:
            return 0
        #定义，i前的最大数组值。

        gl = [0] * n # may or may not include point i
        lo = [0] * n # include point i

        gl = nums[0]
        lo = nums[0]

        for i in range(1, n):
            lo[i] = max(nums[i], lo[i-1] + nums[i]) # lo only have point i or else.
            gl[i] = max(lo[i], gl[i-1])#incude i or not

        return gl[n - 1]