백준 11055번. 가장 큰 증가 부분 수열

백준 11055번. 가장 큰 증가 부분 수열

0. 유사 문제

가장 긴 증가하는 부분

가장 긴 감소하는 부분

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 풀이

• 유사 문제와 비슷하다.
• 다만 길이가 아니라 합이라서 배열을 탐색하면서 합을 찾아야 한다.
• 아무리 작아도 본인 하나 선택한 것보다는 크거나 같기 때문에 d 배열의 초기값을 배열과 똑같이 만들어주었다.

5. 처음 코드와 달라진 점

• 초기값을 배열과 같이 해야겠다고 생각해놓고 아무 생각없이 안 했다.
• sum이라는 변수를 만들었다가 지웠다.
  정신이 멍해서 막 썼다. sum 변수는 심지어 쓰이지도 않았다.

6. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[1000];
int d[1000];

int main(){
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++){
		scanf_s("%d", &arr[i]);
		d[i] = arr[i];
	}
	
	d[0] = arr[0];

	for (int i = 1; i < n; i++){
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) d[i] = max(d[i], d[j]+arr[i]);
		}
	}

	int max_value = d[0];

	for (int i = 1; i < n; i++){
		max_value = max(max_value, d[i]);
	}

	printf("%d", max_value);
}