目录
题目链接
注意点
解法
小结
题目链接
Maximum Subarray - LeetCode https://leetcode.com/problems/maximum-subarray/
注意点
最大值有可能是正负数交替着出现
解法
解法一: 一次遍历即可. 当 sum 小于 0 的时候就重新开始求和, 因为 sum 小于 0 再加上一个数字绝对不可能是 max(即 sum+nums[i] <nums[i]) 时间复杂度为 O(n)
- class Solution {
- public:
- int maxSubArray(vector<int>& nums) {
- int max = nums[0],sum = nums[0],i,n = nums.size();
- for(i = 1;i <n;i++)
- {
- if(sum < 0) // when sum < 0, sum + nums[i] < nums[i]
- {
- sum = nums[i];
- }
- else
- {
- sum += nums[i];
- }
- if(sum> max)
- {
- max = sum;
- }
- }
- return max;
- }
- };
小结
这道题有更多的解法, 但是 O(n) 应该是最快的了. 想起来这个还是我大一的时候从 ACM 培训讲座上学到的
来源: http://www.bubuko.com/infodetail-2945204.html