Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

1
2
3
4
5
Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
1
2
3
4
5
Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
1
2
3
4
5
Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
1
2
3
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104

Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dp = [0] * len(nums)
pre = 0

for i in range(len(nums)):
    cur = pre + nums[i]
    dp[i] = cur
    pre = cur

max_val = float('-inf')
min_val = 0              

for i in range(len(nums)):
    max_val = max(max_val, dp[i] - min_val)
    min_val = min(min_val, dp[i])

return max_val
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]

        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i-1] + nums[i])

        return max(dp)
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):
            cur = max(nums[i],cur+nums[i])
            max_sum = max(max_sum, cur)

        return max_sum
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxsum = float('-inf')
        s = 0
        for i in nums:
            s+=i
            if s>maxsum:
                maxsum = s
            if s<0:
                s=0
        return maxsum