[BOJ 11055] 가장 큰 증가 부분 수열

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

 

풀이 : 

 

DP문제 입니다.

가장 큰 값을 가지는 LIS가 아니라 가장 큰 값을 가지는 증가 부분 수열 이라는 점에 주의합시다.

 

값을 쌓아 가실 때 이전까지 증가 수열 중 현재 값과 증가 수열을 이루면서

가장 큰 값을 갖는 증가수열이 되도록 쌓아가시면 됩니다.

 

#include<stdio.h>
 
int n,arr[1000],cache[1000],max;
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)scanf("%d", &arr[i]);
    for (int i = 0; i < n; i++)
    {
        cache[i] = arr[i];
        for (int j = 0; j < i; j++)if (arr[j] < arr[i] && cache[i] < cache[j] + arr[i])cache[i] = cache[j] + arr[i];
        max = max > cache[i] ? max : cache[i];
    }
    printf("%d", max);
}