BOJ 11055 가장 큰 증가 부분 수열

문제출처 : https://www.acmicpc.net/problem/11055

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

- 1 <= N <= 1,000

  1 <= Ai <= 1,000

2. 접근방법

- LIS와 같음

3. 시간복잡도

- n^2

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001], a[1001], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++){
		d[i] = a[i];
		for (int j = 0; j < i; j++)
			if (a[j] < a[i] && d[i] < d[j] + a[i])
				d[i] = d[j] + a[i];
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]