Requirements:
Given an array of integers, nums, find a contiguous subarray with the largest sum (the subarray contains at least one element) and return its largest sum.
- Example 1
Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code
- Example 2
Input: nums = [1] Output: 1Copy the code
- Example 3
Input: nums = [0] Output: 0Copy the code
- Example 4
Input: nums = [-1] Output: -1Copy the code
- Example 5
Input: nums = [-100000] Output: -100000Copy the code
Rounding out the code
class Solution(object) :
def maxSubArray(self, nums) :
if not nums:
return 0
currSum, result = nums[0], nums[0]
for index in range(1.len(nums)):
currSum = max(nums[index], currSum + nums[index])
result = max(result, currSum)
return result
Copy the code
The most important part of the design is to determine whether the value of the current currSum should be replaced with the new value or the value of the current currSum should be replaced with the new value. The result is to save the historical maximum value.
Data: [– 2, 1, 3, 4, 1, 2, 1, 5, 4]
currSum | result | |
---|---|---|
0 | 2 – | 2 – |
1 | 1 | 1 |
2 | 2 – | 1 |
3 | 4 | 4 |
4 | 3 | 4 |
5 | 5 | 5 |
6 | 6 | 6 |
7 | 1 | 6 |
8 | 5 | 6 |