標準14002/最長成長部分数列4

質問する

に答える

説明:

これは、最大増分部分数列からこの数列に出力される問題です.
前に知っておくべきA[i],D[i]のほかに,V[i]を求める.
V[i]=A[i]の前の数値インデックスが必要です.
つまり、A[i]の前では、A[V[i]の長さが最も長い.

コード#コード#

import java.util.Scanner;

public class Num14002 {
	static int[] a;
    static int[] d;
    static int[] v;
    static void go(int p) {
        if (p == -1) return;
        go(v[p]);
        System.out.print(a[p] + " ");
    }

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        a = new int[n];
        
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        
        d = new int[n];
        v = new int[n];
        
        for (int i=0; i<n; i++) {
            d[i] = 1;
            v[i] = -1;
            for (int j=0; j<i; j++) {
                if (a[j] < a[i] && d[i] < d[j]+1) {
                    d[i] = d[j]+1;
                    v[i] = j;
                }
            }
        }
        
        int ans = d[0];
        int p = 0;
        
        for (int i=0; i<n; i++) {
            if (ans < d[i]) {
                ans = d[i];
                p = i;
            }
        }
        System.out.println(ans);
        go(p);
        System.out.println();
	}

}

コードの説明

注意:
ソース:https://www.acmicpc.net/problem/14002