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

문제 주소: https://www.acmicpc.net/problem/11055

난이도: silver 2

1.문제설명

• 가장 큰 증가 부분순열의 합을 구하는 문제이다.
• 유명한 문제이니 설명은 이정도면 될것이다.

2.문제해결 아이디어.

• 이전에 푼 가장 긴 증가 부분 수열 문제와 비슷하다.

  https://velog.io/@qlql323/%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-11053-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4

• DP를 통해 최적화를 하면된다.

3.문제접근법

• 이중 for문으로 피벗을 정해놓고 dp테이블을 업데이트하면된다.

#DP테이블 선언
dp = [0] * N
dp[0] = nums[0]

#핵심부분
for i in range(1,N): #피벗을 정해놓음 1번부터(0번은 테이블 생성할때 업데이트해줌)
    for j in range(i): #피벗 이전의 원소들을 순회하면서
        if nums[j] < nums[i]: #피벗 이전의 원소보다 피벗의 원소가 더 크면(증가 부분수열이 계속 성립하면)
            dp[i] = max(dp[i], dp[j]+nums[i]) #max(현재값 or j번째 원소까지 증가 부분순열의 합 + i번째 원소의 값)
        else: #증가 부분수열이 끊기면
            dp[i] = max(dp[i], nums[i]) #그냥 쓸지, 아니면 새롭게 시작할지 정함

4.특별히 참고할 사항

• 증가하는 부분순열문제는 2중 for문 형태를 기억하면 비슷한 문제도 쉽게 풀수있을듯하다.

5.코드구현

N = int(input())
nums = list(map(int, input().split()))
dp = [0] * N
dp[0] = nums[0]
for i in range(1,N):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j]+nums[i])
        else:
            dp[i] = max(dp[i], nums[i])
print(max(dp))