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