문제 출처

1. 문제설명

  • 수 N개가 주어졌을 때, 가장 큰 증가하는 부분 수열의 합을 출력하라



2. 알고리즘 설계

  • 흔히 LIS라고 불리는 well-known 알고리즘이다.
  • 로직
    • i번째 인덱스부터 시작한다.
    • DP 배열의 값은 arr의 현재 i번째 인덱스 값으로 초기화 한다.
    • 첫 번째 인덱스부터 i번째 인덱스 값까지 검토한다.
      • 현재 탐색중인 인덱스의 값이 i보다 작다면,
      • DP[i]에는 현재 DP에 저장된 값과 DP에 저장된 값 + 현재 인덱스의 값 중 큰 값으로 갱신한다.
    • 이후 DP 배열에서 가장 큰 값을 찾아주면 그게 정답이 된다.



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1002;
int n, arr[SZ], DP[SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	cout << *max_element(DP, DP+n);
    return 0;
}