Preface
This post carries strong personal sentiment; if you feel uncomfortable reading it, please close it as soon as possible. This post is only a personal learning record. Reposting or sharing within the license terms is welcome; please respect copyright and keep the original link. Thank you for your understanding and cooperation. If you find this site helpful, you can subscribe via RSS. Thanks for your support!
The Problem
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1
1
2
3
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The contiguous subarray [4,-1,2,1] has the largest sum, which is 6.
Example 2
1
2
Input: nums = [1]
Output: 1
Example 3
1
2
Input: nums = [5,4,-1,7,8]
Output: 23
Answer
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max( pre + x, x);
maxAns = max(maxAns,pre);
}
return maxAns;
}
};