leetcodeブラシ問題まとめ、記録、備考53

leetcodeブラシ問題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  [−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray  [4,−1,2,1]  has the largest sum =  6 . 注意!この問題はPAT上の最大のサブ列と少し違いますが、PAT上の問題はすべて負数であれば最大と0であるというヒントはありませんので、その問題と同じ線形時間のアルゴリズムを使うと、論理的な順序で変更する必要があります.まず最大のmaxと比較してから、0との比較を行い、0を置き、次はコードです

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = *nums.begin(), cur = 0;
        vector<int>::iterator it;
        for (it = nums.begin(); it != nums.end(); ++it)
        {
            cur += *it;
            if (cur > sum)
            sum = cur;
            if (cur < 0)
            cur = 0;
        }
        
        return sum;
    }
};

追加要求にはもっと難しい方法がありますが、、しばらく棚上げします...