53. Maximum Subarry

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

**Example:**

1
2
3
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. 思路:我将这种问题理解为“金字塔”问题。每一步结果都建立在前面的基础上,但下一步的结果只需要考虑当前与下一位置的结果(如果不输出过程的话)。这种问题只要将打地基的过程想清楚,循环处理即可。这里的打地基为:如果前面的累加和加上当前位置的值大于当前位置的值,则加上当前位置的值,更新累加和,否则丢弃之前的累加和,更新为当前值。代码如下.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int maxSubArray(vector<int>& nums) {

if (nums.size() == 1) return nums[0];

int res = nums[0];
int sum = nums[0];

for (int i = 1; i < nums.size(); i++) {
sum += nums[i];
if (sum < nums[i]) sum = nums[i];
if (sum > res) res = sum;
}

return res;
}
};
Res. 4ms, Ranking 100.00%.