[백준] 11055 가장 큰 증가 부분 수열, C++

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

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수

www.acmicpc.net

문제 요약

수열 A에서 증가 부분 수열 중 합의 최댓값 찾기

접근

1. 규칙찾기

알고리즘

규칙찾기

새로 알게된 것

dp 너무 어려운데..?

전체 코드

#include <iostream>
#include <algorithm> // max

#define MAX 1000

using namespace std;

int N, answer;
int arr[MAX];
int memo[MAX][MAX];

void printMemo(int size)
{
    for (size_t i = 0; i < size; i++)
    {
        cout << arr[i] << "/\t";
        for (size_t j = 0; j < size; j++)
        {
            cout << memo[i][j] << "\t";
        }
        cout << endl;
    }
    cout << endl;
}

int main()
{
    // 1 init
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];

    // 2 dynamic programming with memoization
    for (int i = 0; i < N; i++)
    {
        answer = max(answer, arr[i]);
        for (int j = i; j < N; j++)
        {
            if (arr[i] < arr[j])
            {
                if (i > 0)
                {
                    memo[i][j] = max(memo[i - 1][j], memo[i][i] + arr[j]);
                }
                else
                {
                    memo[i][j] = arr[i] + arr[j];
                }
            }
            else if (arr[i] == arr[j])
            {
                if (i>0)
                {
                    memo[i][j] = max(arr[i], memo[i-1][j]);
                }
                else
                {
                    memo[i][j] = arr[i];
                }
            }
            else // arr[i] > arr[j]
            {
                if (i > 0)
                {
                    memo[i][j] = memo[i-1][j];
                }
                else
                {
                    memo[i][j] = arr[j];
                }
            }
            answer = max(answer, memo[i][j]);
        }
    }

    // 3 answer
    cout << answer << endl;
    return 0;
}