DP를 사용해 O(N) 시간에 풀었다.
dp[i]를 i번째 인덱스를 오른쪽 끝으로 갖는 구간의 최대합이라 하면 dp[i]는 다음과 같이 구할 수 있다.
if i == 0:
dp[i] = nums[i]
else:
dp[i] = max(0, dp[i-1]) + nums[i]
max(0, dp[i-1])는 새 배열을 시작할 지, 아니면 기존의 배열에다가 i번째 인덱스 값을 넣어줄 지를 결정한다.
Code
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int size = nums.size();
int sum = 0;
int i;
vector<int> dp(size); // dp[i]: i번째 index를 오른쪽 끝으로 갖는 구간의 최대합
dp[0] = nums[0];
for (i = 1; i < size; i++) dp[i] = max(dp[i - 1], 0) + nums[i];
sum = dp[0];
for (i = 1; i < size; i++) sum = max(sum, dp[i]);
return sum;
}
};