1列の数からできるだけ少ない数をふるい取って、左から右を見ると、これらの数は小さいから大きいまで大きいから小さいまでです.
1875 ワード
package cn.xidian.edu.LIS;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class DoubleEndLIS {
public static void main(String[] args) {
int array[] = {1,4,5,3,2,1,4,5,6};
System.out.println(solve(array));
}
private static int solve(int[] array) {
int max = 0;
for (int i = 1; i < array.length; i++) {
int[] part1 = Arrays.copyOfRange(array, 0, i);
int[] part2 = Arrays.copyOfRange(array, i, array.length);
reverse(part2);
// System.out.println(Arrays.toString(part2));
int len1 = solve2(part1);
int len2 = solve2(part2);
if (len1+len2 > max) {
max = len1+len2;
}
}
return array.length-max;
}
private static void reverse(int[] part2) {
for (int start = 0, end=part2.length-1; start < end; start++, end--) {
int t = part2[start];
part2[start] = part2[end];
part2[end] = t;
}
}
private static int solve2(int[] nums) {
//o(n*logn)
int[] LIS = new int[nums.length+1];
LIS[1] = nums[0];
int len = 1;
for (int i = 1; i < nums.length; i++) {
int pos = findPos(LIS, 1, len, nums[i]);
LIS[pos] = nums[i];
if (len < pos) {
len = pos;
}
}
return len;
}
private static int findPos(int[] lIS, int s, int e, int key) {
if (key >= lIS[e]) {
return e+1;
}
while (s <= e) {
int mid = s+(e-s)/2;
if (lIS[mid] > key) {
e = mid-1;
} else if (lIS[mid] < key){
s = mid+1;
} else {
return mid;
}
}
return s;
}
}