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

  예전에 LIS 공부를 조금 해놓아서 그래도 금방 풀었다. 핵심 개념은 결국에 이거다.

 

첫번째 수열부터 쭈우욱 돌면서 i번째 항이 되었을 때! i번째 항이 말한다.

for(int i = 0; i < n; i++)

 

"자. 0번째부터 i-1번째까지 쭉 돌꺼야. 내 밑으로 나와!"

	for(int j = 0; j < i; j++)

그래서 for문을 돌려서 자신보다 작은 녀석들을 찾는다. 그리고 자신보다 작은 녀석에게 묻는다!

		if(seq[i] > seq[j])

"너를 포함한 가장 큰 증가 부분 수열의 합에다가 나를 더하면 내가 현재 가지고 있는 합보다 크냐?!"

max 함수를 통해 크면 가지고 아니면 버린다.

			sum[i] = max(sum[i], sum[j] + seq[i]);

그걸 반복한다.

그리고 마지막으로 for문으로 전체를 훑으면서 제일 큰 sum을 출력하면 끝~

#include <stdio.h>
#include <iostream>
 
using namespace std;

int n;
int seq[1004];
int sum[1004];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> seq[i];
        sum[i] = seq[i];
    }
        
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(seq[i] > seq[j])
            {
                sum[i] = max(sum[i], sum[j] + seq[i]);
            }
        }
    }
    
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        ans = max(ans, sum[i]);
    }
    
    cout << ans;
 
    return 0;
}