[백준 14002, Java] 가장 긴 증가하는 부분 수열4

문제

[https://www.acmicpc.net/problem/14002]

풀이

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] numArray;
    public static int[] longestArrayLength;
    public static ArrayList<Integer>[] increasingArray;

    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numArray = new int[N];
        longestArrayLength = new int[N];
        increasingArray = new ArrayList[N];
        for(int index = 0 ; index<N; index++){
            increasingArray[index] = new ArrayList<Integer>();
        }

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0 ;index<N; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        getLongestIncreasingArray();
        int maxIndex = getMaxIndex();
        bw.write(String.valueOf(longestArrayLength[maxIndex])+"\n");

        Collections.sort(increasingArray[maxIndex]);
        for(int index = 0; index<increasingArray[maxIndex].size();index++){
            bw.write(String.valueOf(increasingArray[maxIndex].get(index)+" "));
        }
        bw.flush();

        br.close();
        bw.close();



    }
    public static void getLongestIncreasingArray(){
        for(int index = 0 ;index<N; index++){
            longestArrayLength[index] +=1;
            increasingArray[index].add(numArray[index]);

            int maxLength = 0;
            int maxIndex = -1;
            for(int backIndex = index-1; backIndex>=0; backIndex--){
                if(numArray[backIndex]<numArray[index]){
                    if(maxLength<longestArrayLength[backIndex]){
                        maxLength = longestArrayLength[backIndex];
                        maxIndex = backIndex;
                    }
                }
            }
            longestArrayLength[index] +=maxLength;
            if(maxIndex!=-1){
                for(int i = 0; i<increasingArray[maxIndex].size();i++){
                    increasingArray[index].add(increasingArray[maxIndex].get(i));
                }
            }
        }
    }

    public static int getMaxIndex(){
        int maxIndex = 0;
        for(int index = 1; index<N; index++){
            if(longestArrayLength[index]>longestArrayLength[maxIndex]){
                maxIndex =index;
            }
        }
        return maxIndex;
    }




}