문제

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

예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다.

---

풀이

풀이과정

최종 코드

#include <iostream>
#include <algorithm> 
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    scanf("%d", &N);
    
    int arr[1001];
    for(int i=1; i<=N; i++) scanf("%d", &arr[i]);

    int dp[1001];
    for(int i = 1; i<=N; i++) dp[i] = arr[i]; //자기만 포함시킬 때로 초기화(자기자신)

    for(int i = 1; i<=N; i++)
    {
        for(int j = 1; j<i; j++)
        {
            if(arr[i] > arr[j]) //내가 더 큰 경우만(오름차순 수열을 위해서)
            {
                dp[i] = max(dp[i], dp[j] + arr[i]); //앞에 j까지 잘 왔을 때, 나를 붙였을 때의 결과중 더 좋은 것을 넣어주기
            }
        }
    }

    sort(dp, dp+N+1);
    printf("%d",dp[N]);

    return 0;
}