가장 큰 증가 부분수열

📍 문제 설명

 

💡 접근

LIS 문제와 거의 동일한 문제

범위에 맞지 않거나(i = 0) 현재의 값이 이전 항들보다 제일 클 수 있으므로 초기화할 때 dp에 arr의 값들을 넣어준다.

2가지 조건을 만족하면 값을 바꿀 수 있다.

1. 이전 항의 숫자가 현재 항의 숫자보다 작아야 더할 수 있다.

2. 이전 항의 합 + 현재 항의 값이 현재 항의 합보다 커야한다.

 

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, answer, min, max;
    static int[][] board;
    static int[] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = kb.nextInt();
        arr = new int[n];
        //dp[n]은 n번째 인덱스를 마지막 항으로 하는 최대 증가 부분 수열
        dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
            dp[i] = arr[i];
        }

        for(int i = 0; i < n; i++) {
            //현재 항의 이전 항들을 탐색
            for(int j = i-1; j >= 0; j--) {
                //1. 이전 항이 현재 항 보다 더 작아야함
                //2. 이전 항의 합 + 현재 항의 값이 현재 항의합보다 더 커야함
                if(arr[j] < arr[i] && dp[j]+arr[i] > dp[i]) {
                    dp[i] = dp[j] + arr[i];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(dp[i] > max) max = dp[i];
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(max);
    }

    private void solution() {
    }

}