백준 11055 c++ 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055

11055번: 가장 큰 증가 부분 수열

---

문제

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

---

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
	int N;
	cin >> N;
	vector<int> dp(1000001, 0);//본인이 가장 큰 값이라고 했을 때 오름수열의 합
	vector<int> arr(1001, 0);//본인 자리의 값을 저장할 벡터
    //입력
	for (int i = 1; i <= N; i++)
	{
		cin >> arr[i];
	}
	dp[1] = arr[1];
	for (int i = 2; i <= N; i++)
	{
		vector<int> index;//인덱스를 담을 벡터
		for (int j = i-1; j >= 1; j--)
		{
			if (arr[j] < arr[i])
			{
				index.push_back(j);//만약 i가 앞에 값보다 크면 앞에 값의 인덱스를 저장
			}
		}
		int plus = 0;
		for (int k = 0; k < index.size(); k++)//저장한 인덱스의 dp(합) 중 가장 큰 걸 plus에 저장
		{
			plus = max(dp[index[k]], plus);

		}
		dp[i] = arr[i] + plus;//i의 dp값은 본인 수 arr[i]에 가장 큰 이전의 dp값을 더한것
	}
	int result = 0;
	for (int i = 1; i <= N; i++)
	{
		result = max(result, dp[i]);//모든 dp값중 가장 큰 걸 출력
	}
	cout << result;
}

---

n = 5 일 때 수열이 다음과 같다고 하자,

1

8

2

3

9

for 문에서 i=5일 때 9를 가리킨다

9는 이전의 3보다 수가 크기 때문에 if문에 걸리고 3뿐만 아니라 2, 8, 1도 걸리기 때문에 

4, 3, 2, 1 인덱스가 index vector에 저장되게 된다.

이제 이 index안에서 for문을 돌려 가장 큰 dp 값을 가진 인덱스를 찾게되고

그 dp값에 9를 더한값이 dp[5]가 되게 된다.