【LeetCode】53. Maximum Subarray
1856 ワード
53. Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
【分析】
この問題に対して、非常に直観的な解法はすべてのサブ配列を遍歴し、二重ループを採用すれば完成するが、N個の要素の配列に対して、その群数はN(N+1)/2であり、アルゴリズムの時間複雑度はO(N 2)である.これは明らかに「暴力」の解法だ.テーマの例では、簡単に分析して、その法則を見つけることができます.【解法及び注釈】
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
[−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray [4,−1,2,1] has the largest sum = 6 . 【分析】
この問題に対して、非常に直観的な解法はすべてのサブ配列を遍歴し、二重ループを採用すれば完成するが、N個の要素の配列に対して、その群数はN(N+1)/2であり、アルゴリズムの時間複雑度はO(N 2)である.これは明らかに「暴力」の解法だ.テーマの例では、簡単に分析して、その法則を見つけることができます.
[−2,1,−3,4,−1,2,1,−5,4]の場合、sumはsum=nums[0]=−2を初期化する.sum+nums[1]class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum,maxSum;
if(nums.empty())return 0;// ， 0
sum=maxSum=nums[0];//
for(int i=1;i<nums.size();i++)
{
if(nums[i]>sum+nums[i])// ，
{
sum=nums[i];
if(sum>maxSum)maxSum=sum;//
}
else
{
if(sum>sum+nums[i]&&sum>maxSum)// ， 、
maxSum=sum;
sum+=nums[i];
}
}
if(sum>maxSum)maxSum=sum;//
return maxSum;
}
};