最长递增子序列 java_动态规划深入6 最长递增子序列
也就是不需要连续，只要暗藏递增序列就累加起来。
我一开始以为必须连续的，题目没看清就写了，尴尬。后来仔细一看，不对。
然后经过仔细研究题目发现，这就是一道比较简单的动态规划的题目。和前面写的题目都有些相似，所以建模一下子就建立出来了。
用一个dp数组存放每个位置的最优解。
状态传递式就是：当array[i]>array[j]时，就dp[i]=dp[j]+1;其中j是遍历小于i的位置。然后记住最大的dp[i]就ok了。
然后来看我写的代码：
public static void main(String[] args) {
int[] array = { 10, 9, 2, 5, 3, 7, 101, 1, 18 };
int len = getLongthOfLIS(array);
System.out.println(len);
}
private static int getLongthOfLIS(int[] array) {
int[] dp = new int[array.length];
dp[0] = 1;
int result = 1;
for (int i = 1; i < dp.length; i++) {
int max = 1;// 局部变量max用于存储dp[i]上的最大值，最后再传递给dp[i]
dp[i] = 1;// 所有dp[i]必须初始化为1，不然默认为0，然后输出的时候你就发现不对了
for (int j = i; j >= 0; j--) {
if (array[i] > array[j]) {
dp[i] = dp[j] + 1;
if (max < dp[i]) {
max = dp[i];// 取出最大的dp[i]
}
}
}
dp[i] = max;// 最后的时候进行赋值
if (result < dp[i]) {
result = dp[i];// 这里直接有个全局变量，用于当作返回值
}
}
System.out.println(Arrays.toString(dp));// 输出数组，测试是否正确
return result;
}
刚开始的时候脑子有点抽了，总觉得应该更简单，就不愿意写复杂，结果半小时没写出来，然后还是老老实实地定义变量，双重遍历，不断比较取出最大值。把思路非常清晰地表达出来很重要，看清题目很重要。
对了，我看网上很多人的第二个for循环和我写的不太一样。就是比如：
for(int j=0;j
if(array[j]list[i]){
list[i] = list[j]+1;
}
}
里面用了个逻辑与的运算，先判断是否可以加1，然后判断是否比原来的dp[i]大，全部符合条件了再赋值dp[i]，其实这样的话，思路和我的差不多，只不过我定义了临时变量存储了最大值，所以我感觉我的看起来更容易看懂，但是没有他们的这么简洁。各有各的优势吧。
欢迎交流讨论。