Maximum Subarray

problem

주어진 배열에서 연속된 배열의 최댓값을 찾는 문제이다.

solution

brute force

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

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

알게된 것

Dynamic programming -> 문제가 작은 문제로 나눠질 경우, 이미 푼 문제는 다시 풀지않고 값을 저장해서 쓴다.

Kadane’s Algorithm