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

https://www.acmicpc.net/problem/11055

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

역시 dp

수열 A를 받는다.

A를 베껴 dp를 만든다.

dp[i]=A[i]를 끝으로 하는 수열의 가장 긴 길이이다.

A[i]부터 왼쪽으로 탐색하면서

A[i]보다 작은 값들중 가장 큰 A[?]를 구하고

dp[?]에다가 a[i]를 더한 값이 dp[i]이다.

이후 가장 큰 dp[?]를 구한다.

n=int(input())a=[* map(int,input().split())]dp=a.copy()
for i in range(1,len(dp)):    max_cnt=0    for j in range(len(a[:i])):
        if a[j]<a[i]:            max_cnt=max(max_cnt,dp[j])
    dp[i]=dp[i]+max_cntprint(max(dp))