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

문제 링크입니다: https://www.acmicpc.net/problem/11055

LIS(Largest Increasing Sequence) 문제와 비슷하지만 증가 부분 수열의 최대 길이가 아닌 최대합인 점에서 달랐습니다.

/*

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

 

int N;

int arr[MAX];

int cache[MAX];

 

int maxSum(void)

{

        int result = 0;

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

        {

               cache[i] = arr[i];

               //i번째 인덱스가 최대 증가부분수열의 마지막인 경우의 합을 캐시에 저장

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

                       if (arr[i] > arr[j] && cache[i] < cache[j] + arr[i])

                              cache[i] = cache[j] + arr[i];

               result = max(result, cache[i]);

        }

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N < 1 || N>MAX)

               exit(-1);

 

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

               cin >> arr[i];

 

        cout << maxSum() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략