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

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

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

 문제 설명 

 

수열 이 주어지는데 그 수열에서 증가 부분 수열의 합중 최대값을 찾는 것 .

{1 100 2 3 4} : 증가 부분 수열 X     {1 2 3 5 7 50} : 증가 부분 수열 O

 

 알고리즘 

 

순서대로 진행하며 자기보다 낮은 인덱스를 조사. 

그중 자기보다 낮은수에 대해 증가 부분 수열 합을 구한다.

그래서 나오는 최댓값을 자기 인덱스 DP 에 대입 한다.

 

 

 코드  

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    int N;
    cin >> N;
    int arr[1001];
    int dp[1001];
    for (int i = 0; i < N; i++)cin >> arr[i];
 
    for (int i = 0; i < N; i++)dp[i] = 0;
 
    for (int i = 0; i < N; i++) {
        int num = 0;
        for (int j = i; j >= 0; j--) {
            
            if (arr[i] > arr[j]) {//자기보다 낮은 인덱스에서 낮은 값을 발견 했다 .
 
                num =max(num, arr[i] + dp[j]); //그중 최대값을 찾는 .
 
            }
            
            
        }
        dp[i] = num;
        if (dp[i] == 0)dp[i] = arr[i];// 자기 아래 인덱스에서 자기 보다 낮은숫자가 없으면 그냥 자기를 DP 배열에 넣음.
    }
    int result = 0;
 
    for (int i = 0; i < N; i++) {
        result = max(result, dp[i]);
    }
    cout << result;
 
}