개요

수열 arr에서 연속되거나 그렇지않은 부분수열이 증가할때 해당 부분수열의 모든 원소의 합이 최댓값을 구하는 알고리즘이다.
최대 증가 부분수열 알고리즘이라고 한다.

구현

	int MSIS(vector<int> & arr) {
		//계산불가능 한 경우
		if (arr.empty()) return 0;
		
		//DP로 계산될것.
		vector<int> dp(arr.size());

		//초깃값
		dp[0] = arr[0];

		for (int i = 1; i < arr.size(); i++) {
			//j < i인 모든 j에대해 arr이 증가하고있고, 
			//이전합(dp[j])이 현재최대합dp[i]보다 크면 dp[i]를 dp[j]로 변경
			for (int j = 0; j < i; j++) 
				if (arr[j] < arr[i] && dp[j] > dp[i]) dp[i] = dp[j];

			//현재 arr[i]를 dp에 포함시킴
			dp[i] += arr[i];
		}

		// 찾은 0~i까지의 부분수열의 최대합 중 최대 부분수열의 합을 찾아서 리턴
		int res = 0;
		for (int x : dp) res = std::max(res, x);
		return res;
	}

i보다 작은 j들을 하나씩 살펴보며, 현재 dp[i]값을 작성할것인데,
이때 arr[j] < arr[i] : 증가하고있고, 이때
dp[j] > dp[i] : 이미 구한값 dp[j]가 크면
dp[i] = dp[j]로 작성하는 간단한 과정이다.
모든 j를 탐색후, 마지막으로 현재 원소를 dp[i]. 부분수열합에 추가해주면 된다.

모든 dp를 구한뒤, 그중 최댓값을 찾아서 리턴하면 MSIS가 구해진다.

한계

그리디 방법으로 구하면 N^2 이나 알고리즘 사용시 (1/2)N^2이나 어찌됬든 O(N * N)이 걸리는 알고리즘이다.

관련문제

https://www.acmicpc.net/problem/11055 >> https://velog.io/@cldhfleks2/11055