53. Maximum Subarray

c++ Leetcode

https://leetcode.com/problems/maximum-subarray/ 与えられた値を1つずつ足していき、最も大きな値を選ぶ総当りは思いついたが、O(ｎ2)で遅い。

部分配列をO(ｎ)で計算するKadane Algorithm というアルゴリズムがあるようでした。

Kadaneのアルゴリズム—（動的計画法）—どのようにそしてなぜそれが機能するのか？

総当り

class Solution {
public:
    int max_sum = INT_MIN;
    int maxSubArray(vector<int>& nums) {
        for(int i = 0; nums.size() > i; i++){
            int currrent_sum = 0;
            for(int j=i; nums.size() > j; j++){
                currrent_sum += nums[j];
                max_sum = max(max_sum, currrent_sum);
            }
        }
        
        return max_sum;
    }
};

Kaneda Algorithm

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = INT_MIN;
        int tmpSum = 0;
        for(int i =0; i < nums.size(); i++){
            tmpSum = max(nums[i], nums[i] + tmpSum);
            if(tmpSum > max_sum){
                max_sum = tmpSum;
            }
        }
        return max_sum;
    }
};