[LeetCode] 53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

Maximum Subarray - Easy

 

배열이 주어졌을때, 이 배열의 연속된 부분 배열의 합의 최대값을 구하는 문제다.

 

처음 최대값 ret을 INT_MIN (-2^31) 으로 두고, 합을 나타내는 S를 0으로 두자.

그 뒤 배열을 훑으며 S = S + 해당값 으로 바꿔주고, ret = max(ret, S) 로 바꿔주자.

그런 뒤, S가 만약 마이너스 값이라면, 이 다음 값에서 S와 그 값을 더하는 것보다 그냥 다음 값에서 새로 출발하는 것이 나으니 S=0으로 바꿔주자.

 

-2 1 -3 4 -1 2 1 -5 4 를 예로 들면,

배열	-2	1	-3	4	-1	2	1	-5	4
S	-2=>0	1	-2=>0	4	3	5	6	1	5
ret	-2	1	1	4	4	5	6	6	6

이와 같이 진행해 주면 된다.

 

전체 풀이 코드

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