백준 : 11055번 가장 큰 증가하는 부분 수열 (c++)

백준 링크

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	45945	20692	16444	44.644%

문제

수열 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의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

예제 입력 1

10
1 100 2 50 60 3 5 6 7 8

예제 출력 1

113

예제 입력 2

10
2 11 3 14 1 200 100 5 101 13

예제 출력 2

228

코드 풀이

1. Array 배열과 dp 배열에 값 대입
2. 2중 포문을 돌면서 값 비교 (안쪽 포문에서 j < i 부분이 중요)
3. Array[j]가 Array[i]보다 작다면 수열조건 성립
4. dp 최대값으로 갱신

코드

#include <iostream>
#include <algorithm>

using namespace std;

int Array[1001];
int dp[1001];

int Func(int Index)
{

	for (int i = Index; i >= 0; --i)
	{
		int Max = *max_element(dp, dp + i);

		if (Max < Array[Index] + Max)
			return Max;
	}

	return 0;
}

int main() 
{
	int N;

	cin >> N;

	for (int i = 0; i < N; ++i) 
	{
		cin >> Array[i];
		dp[i] = Array[i];
	}

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < i; ++j)
		{
			if (Array[j] < Array[i])
			{ 
				dp[i] = max(dp[i], dp[j] + Array[i]);
			}
		}
	}
	
	cout << *max_element(dp, dp + N);

	return 0;
}