Baekjun-最長のVitonic部分数列[1054]

11614 ワード
アルゴリズム#アルゴリズム# Java ダイナミックプログラミング テキストリンク
質問する
数列SはいくつのSkをベースにして、S 1 Sk+1 > ... SN−1>SNが満足すれば,その数列を頼むニック数列と呼ぶ.
例えば、{10、20、30、25、20}および{10、20、30、40}、{50、40、25、10}はバイナリ数列であり、{1、2、3、2、1}および{10、20、30、40、20、30}はバイナリ数列ではない.
数列Aが与えられた場合、その数列の2進数列および最長数列の長さを計算するプログラムを作成します.
入力
1行目には数列Aの大きさNが与えられ、2行目には数列AのAiが与えられる.(1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
しゅつりょく
1行目は、数列Aの部分数列のうち最も長い2進数列の長さを出力する.
に答える
この問題は,最長増分部分数列の応用問題と考えられる.お願いニック数列とは、昇順に増加し、降順に減少する数列です.
例えば、入力例として与えられる1 5 2 1 4 4 5 1
増加した部分数列長の値r d[]=1,2,1,3,4,5,2,1が認められた.減少した部分数列の長さは、入力例の最後の部分(右端)から、逆順に増加した部分数列、l d[]=1、5、2、1、4、3、2、1を求めることができる.
今一番長いお願いニック部分の数列を求める方法は、上の2つのリストを加算することです.ただし、マージされたリストの要素が重複しているため、-1を行う必要があります.
理解を助けるために、2番目のインデックス部分を見てみましょう.
増加部分数列の2番目のr d[1]は2であり、減少部分数列の2番目のl d[1]は5である.
r d[1]={1,5},l d[1]={5,4,3,2,1}(元の数列の左側から)
2つを合わせると{1,5,5,4,3,2,1,}なので長さは6です.
要するに,最長成長の部分数列を先に求め,次いで逆順に最長成長の部分数列を求め,2つを加算した値に−1を加算する.そして最大の値を出力すればいいです.
ソース
import java.util.*;

public class Main {
	public static int n;
	public static int[] arr;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}

		// 증가하는 부분수열
		int[] d = new int[n];
		Arrays.fill(d, 1);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					d[i] = Math.max(d[i], d[j] + 1);
				}
			}
		}

		// 감소하는 부분수열
		int[] d2 = new int[n];
		Arrays.fill(d2, 1);

		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				if (arr[j] < arr[i]) {
					d2[i] = Math.max(d2[i], d2[j] + 1);
				}
			}
		}

		int ans = d[0] + d2[0] - 1;
		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, d[i] + d2[i] - 1);
		}
		System.out.println(ans);
	}

}
Flutter実戦のカスタムログ印刷コンポーネント
コトリンDB