算法编程

思路

dp算法，但是题目需要多组输入，所以动归不是关键啦
题目的样例有误导性，没有负数啊。。。。
还有，输出最长数组就行了，不用输出一个数字表示长度

代码

第一题，88%

package Alibaba;import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;/*** Created by luzhonghao on 16/4/25.*/
public class Main {public static  int LISS(int array[], int length, int result[]){int i, j, k, l, max;//递增子序列中最大值最小的子序列的最后一个元素（最大元素）在array中的位置int [] liss = new int[length];//前驱元素数组，用于打印序列int [] pre = new int[length];liss[0] = 0;for(i = 0; i < length; ++i){pre[i] = i;}for(i = 1, max = 1; i < length; ++i){//找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中，j最小j = 0;k = max - 1;while(k - j > 1){l = (j + k) / 2;if(array[liss[l]] < array[i]){j = l;}else{k = l;}}if(array[liss[j]] < array[i]){j = k;}//array[liss[0]]的值也比array[i]大的情况if(j == 0){//此处必须加等号，防止array中存在多个相等的最小值时，将最小值填充到liss[1]位置if(array[liss[0]] >= array[i]){liss[0] = i;continue;}}//array[liss[max -1]]的值比array[i]小的情况if(j == max - 1){if(array[liss[j]] < array[i]){pre[i] = liss[j];liss[max++] = i;continue;}}pre[i] = liss[j - 1];liss[j] = i;}//输出递增子序列i = max - 1;k = liss[max - 1];while(pre[k] != k){result[i--] = array[k];k = pre[k];}result[i] = array[k];return max;}public static void main(String[] args) {Scanner s = new Scanner(System.in);while (s.hasNext()) {String line = s.nextLine();line = line.trim();if (line.equals("")) {System.out.println("");continue;}// System.out.println(line);String patternStr = "[-\\d+\\s*]+";Pattern p = Pattern.compile(patternStr);Matcher m = p.matcher(line);boolean flg = m.matches(); if (flg) {String[] content = line.split(" ");ArrayList<Integer> iArrayList = new ArrayList<Integer>();//              int i = 0;boolean stop = false;for (String sc : content) {if (!sc.equals("")) {try {int temp = Integer.valueOf(sc);iArrayList.add(temp);
//                          input[i++] = temp;} catch (Exception e) {stop = true;break;}}}if (stop == false && iArrayList.size() > 0) {int [] input = new int [iArrayList.size()];int i = 0;for (int item : iArrayList) {input[i++] = item;}int[] result = new int[i];int ret = LISS(input, input.length, result);for (int j = 0; j < ret; ++j) {if (j == ret - 1) {System.out.println(result[j]);} else {System.out.print(result[j] + " ");}}}}}}
}

第二题，78%

package first;import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;/*** Created by luzhonghao on 16/4/25.*/
public class Main {public static  int LISS(int array[], int length, int result[]){int i, j, k, l, max;//递增子序列中最大值最小的子序列的最后一个元素（最大元素）在array中的位置int [] liss = new int[length];//前驱元素数组，用于打印序列int [] pre = new int[length];liss[0] = 0;for(i = 0; i < length; ++i){pre[i] = i;}for(i = 1, max = 1; i < length; ++i){//找到这样的j使得在满足array[liss[j]] > array[i]条件的所有j中，j最小j = 0;k = max - 1;while(k - j > 1){l = (j + k) / 2;if(array[liss[l]] < array[i]){j = l;}else{k = l;}}if(array[liss[j]] < array[i]){j = k;}//array[liss[0]]的值也比array[i]大的情况if(j == 0){//此处必须加等号，防止array中存在多个相等的最小值时，将最小值填充到liss[1]位置if(array[liss[0]] >= array[i]){liss[0] = i;continue;}}//array[liss[max -1]]的值比array[i]小的情况if(j == max - 1){if(array[liss[j]] < array[i]){pre[i] = liss[j];liss[max++] = i;continue;}}pre[i] = liss[j - 1];liss[j] = i;}//输出递增子序列i = max - 1;k = liss[max - 1];while(pre[k] != k){result[i--] = array[k];k = pre[k];}result[i] = array[k];return max;}public static void main(String[] args) {Scanner s = new Scanner(System.in);if (s.hasNext()) {String line = s.nextLine();line = line.trim();if (line.equals("")) {System.out.println("error");
//              continue;}// System.out.println(line);String patternStr = "[-\\d+\\s*]+";Pattern p = Pattern.compile(patternStr);Matcher m = p.matcher(line);boolean flg = m.matches(); if (flg) {String[] content = line.split(" ");ArrayList<Integer> iArrayList = new ArrayList<Integer>();//              int i = 0;for (String sc : content) {if (!sc.equals("")) {try {int temp = Integer.valueOf(sc);iArrayList.add(temp);
//                          input[i++] = temp;} catch (Exception e) {System.out.println("error");return;}}}if (iArrayList.size() > 0) {int [] input = new int [iArrayList.size()];int i = 0;for (int item : iArrayList) {input[i++] = item;}int[] result = new int[i];int ret = LISS(input, input.length, result);for (int j = 0; j < ret; ++j) {if (j == ret - 1) {System.out.println(result[j]);} else {System.out.print(result[j] + " ");}}}} else {System.out.println("error");}}}
}

最后没来及改，在判断有2-之类的错误输入的时候，应该是直接输出error，第一题是直接输出换行。

关键点在正则：一定要把Java正则表达式搞清楚。

其他论述题

sleep和wait区别
抽象类和接口区别
runnable和thread区别