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

이 문제 푸는데 삽질을 엄청 엄청 많이 했다.. 다시 생각해도 눈물난다..

첫 번째 아이디어
dp를 2차원 vector로 만들어서 d[y][x]의 값은 A[y]에서 시작해서 A[x]에서 끝나는 합을 저장하고 저장 할 때마다 result 에 있는 값과 비교해 큰 값을 갱신해 주는 방법으로 했다.

y>=x 인 경우는 필요없다-실제 코드에서는 메모리 할당하면서 다 0으로 초기화를 했다.
(문제에서 N의 범위가 1<=N<=100,000 이라고 했기 때문에 N이 MAX인 경우 엄청난 메모리 낭비다. 이때 풀면서도 잘못됨을 느꼈다..)

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

	vector<vector<int>>dp(k, vector<int>(k, 0));
	int result = A[0];
    	
        for (int y = 0; y<k-1; y++) {

		dp[y][y + 1] = A[y] + A[y + 1];
        
		for (int x = y + 1; x < k-1; x++) {
			dp[y][x] = dp[y][x - 1] + A[x];
            
			result = max(result, dp[y][x]);
		}
	}
 }
    

답은 정확하게 나오지만 아니나 다를까 메모리 초과

두 번째 아이디어
dp배열에서 메모리 낭비가 많이 되니까 실제로 값을 넣어야 하는 부분만 메모리 할당을 했다.
일단 vector<vector>dp(k); 이차원 vector를 선언 하면서 y축만 메모리 k크기만큼 할당하고 값이 들어올 때마다 x를 push_back()하며 추가했다.

실제로 이렇게 메모리가 할당 되었는지 잘 모르겠다. 확인을 안 해봤다.

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

	int result = A[0];

	for (int y = 0; y<k-1; y++) {
                         
		dp[y].push_back(A[y] + A[y + 1]);

		for (int x = y + 1; x < k-1; x++) {

			dp[y].push_back(dp[y].front()+A[x]);

			result = max(result, dp[y].front());
		}
	}

	return result;
}

또 메모리 초과..

세 번째 아이디어
dp를 일차원 벡터로 만든다. dp[i]는 i번째에서 끝나는 제일 큰 연속합을 저장한다. dp[i]=dp[i-1]+A[i]
하지만 A[i]의 값이 d[i-1]+A[i]의 값보다 클 수 있다.
예를 들면 {1, -3, 5} 의 경우 dp[2]=dp[1]+A[2] 즉, -2+5=3 보다 A[2]인 5의 값이 더 크다.
dp[i]<dp[i-1]+A[i] 인 경우에만 dp[i]를 갱신해준다.

#include<iostream>
#include<vector>

using namespace std;
const int MAX = 100000;

int maxSum(const vector<int>& A, int k) {
	int dp[MAX];
	int result = dp[0] = A[0];

	for (int i = 1; i < k; i++) {
		dp[i] = A[i];

		if (dp[i] < dp[i - 1] + A[i])
			dp[i] = dp[i - 1] + A[i];

		result = max(result, dp[i]);
	}
	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;
}

동적 프로그래밍 할 때는 점화식만 잘 세우면 된다 제발!!
그리고 Baekjoon #11055 가장 큰 부분 증가수열 문제를 풀 때랑 로직이 거의 비슷한데 삽질을 엄청 했다.. 제대로 복습을 안 했나보다..
그래도 이것 저것 하면서 2차원 vector 메모리 할당하는 방법을 익혔다..