Maximum Subarray

Quesiton

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)?

Analysis

Test Cases:

• empty array
• all negative array

Thoughts

跟continuous maximum subsequence一样，用DP做 dp[i]存以i为终点的subarray的最大sum

当前`index`为`i`
if dp[i-1] < 0(以i-1为终点的最大结果为负)， 当前dp[i] = nums[i]
else , dp[i] = dp[i-1] + nums[i]

local 与 global

state

• local[i] - 包括第i个元素的最大值
• global[i] - 全局前i个元素中能够找到的最大值

function

local[i] = max(local[i-1] + nums[i], nums[i])
global[i] = max(global[i-1], local[i])

init

local[0] = global[0] = nums[0]

result

global[len(nums)-1]

Solution

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
        if not nums:
            return 0
        currentSum = 0
        length = len(nums)
        maxSum = sys.maxint * -1
        for i in range(length):
            if currentSum < 0:
                currentSum = nums[i]
            else:
                currentSum += nums[i]
            if maxSum < currentSum:
                maxSum = currentSum
        return maxSum