动态规划(六)

最长上升子序列

给定一个整数序列，求，其中最长上升子序列长度。(不要求子序列一定是连续的，只要相对位置不变即可)

• [ 10, 9, 2, 5, 3, 7, 101, 18 ], 其中最长上升子序列长度为4
  最长上升子序列为[ 2, 5, 7, 101]

解法
LIS(i)表示以第i个数字结尾的最长上升子序列的长度。
LIS(i)表示0-i范围内，选择数字nums[i]可以获得的最长上升子序列长度。

LIS(i) = max( 1 + LIS(j) if(nums[i]>nums[j]) )
         j < i

对应的第 i 个数字的上升子序列为：之前第 nums[j]（nums[j]<nums[i]）的上升子序列的最大长度+1

如：

[ 10, 9, 2, 5, 3, 7, 101, 18]

num\i	0	1	2	3	4	5	6	7
10	1
9		1
2			1
5				2
3					2
7						3
101							4
8								4

其中i代表第i个元素的升序子序列最大长度。

1. 第0个元素为10的最大升序序列为自己，即1
2. 第1个元素为9，之前没有比9小的元素，所以最大升序长度为1
3. 第2个元素为2，之前没有比2小的元素，所以最大升序长度即1
4. 第3个元素为5，之前的元素2比5小，所以最大升序长度为2的最大升序长度+1，即1+1=2
5. 第4个元素为3，之前的元素2比5小，所以最大升序长度为2的最大升序长度+1，即1+1=2
6. 第5个元素为7，之前的元素2，5，3都比7小，选择最大的升序长度+1，即2+1=3
7. 第6个元素为101，选取之前比他小的最大升序元素的值+1，即3+1=4
8. 第7个元素为8，选取之前比他小的最大升序元素的值+1，即3+1=4

最后，得到的最大升序长度为4

编码实现

    int lis(int[] arr) {
        if (arr == null) {
            return -1;
        }
        if (arr.length <= 1) {
            return arr.length;
        }
        int len = arr.length;
        int[] memo = new int[len];
        Arrays.fill(memo, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    memo[i] = Integer.max(memo[i], memo[j] + 1);
                }
            }
        }
        return max(memo);
    }

    private int max(int[] array) {
        if (array == null) {
            throw new IllegalArgumentException("The Array must not be null");
        } else if (array.length == 0) {
            throw new IllegalArgumentException("Array cannot be empty.");
        } else {
            int max = array[0];

            for (int j = 1; j < array.length; ++j) {
                if (array[j] > max) {
                    max = array[j];
                }
            }

            return max;
        }
    }

时间复杂度O(n^2)

---

Wiggle Subsequence

一个序列，他的相邻数字的大小关系是升序降序轮流交替，（最初可以是升序，也可以是降序），就称为wiggle sequence,比如：[1, 7, 4, 9, 2, 5]就是一个wiggle sequence，但是[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]就不是，给出一个数组，求出他的最长wiggle sequence的序列。