結果

問題 No.209 Longest Mountain Subsequence
コンテスト
ユーザー Grenache
提出日時 2015-05-16 10:56:11
言語 Java
(openjdk 23)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,591 bytes
コンパイル時間 2,984 ms
コンパイル使用メモリ 78,376 KB
実行使用メモリ 65,388 KB
最終ジャッジ日時 2024-07-06 04:44:24
合計ジャッジ時間 5,689 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.Scanner;

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

		int t = sc.nextInt();

		for (int tcase = 0; tcase < t; tcase++) {
			n = sc.nextInt();
			a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			ldp = new int[n][n];
			rdp = new int[n][n];
			for (int i = 0; i < n; i++) {
				Arrays.fill(ldp[i], -1);
				Arrays.fill(rdp[i], -1);
			}

			int max = 0;
			for (int j = 0; j < n; j++) {
				int lmax = 0;
				for (int i = 0; i < j; i++) {
					lmax = Math.max(lmax, L(i, j));
				}
				
				int rmax = 0;
				for (int k = j + 1; k < n; k++) {
					rmax = Math.max(rmax, R(j, k));
				}
				
				max = Math.max(max, lmax + 1 + rmax);
			}
			
			System.out.println(max);
		}
		
		sc.close();
	}

	private static int n;
	private static int[] a;
	
	private static int[][] ldp;
	private static int[][] rdp;

	private static int L(int i, int j) {
		if (ldp[i][j] != -1) {
			return ldp[i][j];
		}
		if (i == j || a[j] - a[i] <= 0) {
			return ldp[i][j] = 0;
		}

		int ret = 1;
		for (int k = 0; k < i; k++) {
			if (a[j] - a[i] > a[i] - a[k]) {
				ret = Math.max(ret, L(k, i) + 1);
			}
		}

		return ldp[i][j] = ret;
	}

	private static int R(int i, int j) {
		if (rdp[i][j] != -1) {
			return rdp[i][j];
		}
		if (i == j || a[i] - a[j] <= 0) {
			return rdp[i][j] = 0;
		}

		int ret = 1;
		for (int k = j + 1; k < n; k++) {
			if (a[i] - a[j] > a[j] - a[k]) {
				ret = Math.max(ret, R(j, k) + 1);
			}
		}

		return rdp[i][j] = ret;
	}
}
0