53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input:
 [-2,1,-3,4,-1,2,1,-5,4],

Output:
 6

Explanation:
 [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

(1) Java



(2) Python

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        rst = nums[0]
        current = 0
        for num in nums:
            current += num
            if current <= num:
                current = num
            rst = max(rst, current)
        return rst

(3) Scala



results matching ""

    No results matching ""