版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/shiliang97/article/details/102086949
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
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.
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max=nums[0],sum=nums[0];
for(int i=1;i<nums.size();i++){
if(sum<0)sum=0;
sum+=nums[i];
if(sum>=max) max=sum;
}
return max;
}
};