Maximum Subarray

Source

• lintcode: 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)?

Python

import sys
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.maxint-1
        sum=0
        for n in nums:
            if sum>=0:
                sum+=n
            else:
                sum=n
            maxSum = max(maxSum, sum)
        return maxSum