<Baekjoon>#13398연속합2 (Largest sum of continuous subarray) c++

앞에서 푼 연속합의 문제와 다른 점은 수열에서 수를 하나 제거할 수도 있고 안 해도 된다는 것이다.
표를 그리면서 여러가지 생각을 했다.
(dynamic programming 진짜 안 풀린다..)

먼저 한 생각은 연속된 수가 0보다 크거나 같은 양수일 경우에는 그냥 더하고 음수일 경우에 조건문에서 뭔가를 처리해야 하나? 싶었다.
A[i]<0 일 경우에 dp를 하나씩 추가하면서 음수를 하나씩 삭제하는 경우를 생각해서 만들어본 표

표를 보면 알 수 있듯이 음수가 앞으로 몇 번이나 나올줄 모르니까 dp를 얼마나 만들어야 할 지도 모르고, for문이 0에서 9까지 도는 동안 dp[0], dp[1], dp[2],...의 값을 비교해서 가장 큰 수를 result에 저장하는 for문을 또 돌아야한다.

말도 안 되니까 다시 간단한 로직을 생각해보자 !!

dp[i][0], dp[i][1] 배열을 만든다.
dp[i][0]에는 수열에서 수를 제거하지 않을 때 연속합의 최댓값을 저장하고, dp[i][1]에는 하나가 삭제될 때 연속합의 최댓값을 저장한다.

dp[i][0]은 앞에서 했던 것과 마찬가지로, dp[i-1][0]+A[i]와 A[i]중 큰 값을 저장
dp[i][1]은 dp[i-1][1]+A[i]와 dp[i-1][0]중 큰 값을 저장
(여기서 dp[i-1][0])을 저장한다는 말은 A[i]값을 제거하고 연속합을 구하겠다는 말이다)
이해가 안 될 때는 간단한 예제를 표로 만들어보자!

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
const int MAX = 100000;

int maxSum(const vector<int>& A, int k) {

	int dp[MAX][2];
	int result = dp[0][0] = dp[0][1] = A[0];

	for (int i = 1; i < k; i++) {

		dp[i][0] = max(A[i], dp[i - 1][0] + A[i]);
		dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + A[i]);
		result = max({ result, dp[i][0], dp[i][1] });
	}

	return result;
}

int main() {
	int k;
	cin >> k;

	if (k > MAX)
		exit(EXIT_FAILURE);

	vector<int>A(k);

	for (int i = 0; i < k; i++)
		cin >> A[i];

	cout << maxSum(A, k) << endl;

	return 0;
}

막상 코드를 짜보면 진짜 간단해서 허탈하다