LeetCode-最長遞增子序列&和最大的遞增子序列

1.求最長遞增子序列長度

方法一：動态規劃O（n2） 

dp[i]:以i結尾的最長遞增子序列

初始化：dp[*]=1

公式:dp[i]=max(dp[j]+1) and nums[i] > nums[j]，0<=j<i

結果：max(dp)

public static int findLongest2(int[] A) {
		int n = A.length;
		int[] f = new int[n];// 用于存放f(i)值；
		f[0] = 1;// 以第a1為末元素的最長遞增子序列長度為1；
		int maxLen = Integer.MIN_VALUE;
		for (int i = 1; i < n; i++)// 循環n-1次
		{
			f[i] = 1;// f[i]的最小值為1；
			for (int j = 0; j < i; j++)// 循環i 次
			{
				if (A[j] < A[i] && f[j] +1 > f[i]) {
					f[i] = f[j] + 1;// 更新f[i]的值。
					maxLen = Math.max(maxLen, f[i]);
				}
			}
		}

		return maxLen;
	}
           

方法二：O（nlogn）

思路：

例子：假設存在一個序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出來它的LIS長度為5。

定義一個序列B，與的d同大小。

此外，我們用一個變量Len來記錄現在最長算到多少了

首先，把d[1]有序地放到B裡，令B[1] = 2，就是說當隻有1一個數字2的時候，長度為1的LIS的最小末尾是2。這時Len=1

然後，把d[2]有序地放到B裡，令B[1] = 1，就是說長度為1的LIS的最小末尾是1，d[1]=2已經沒用了，很容易了解吧。這時Len=1

接着，d[3] = 5，d[3]>B[1]，d[3]=5，就是說長度為2的LIS的最小末尾是5，很容易了解吧。這時候B[1..2] = 1, 5，Len＝2

再來，d[4] = 3，它正好加在1,5之間，放在1的位置顯然不合适，因為1小于3，長度為1的LIS最小末尾應該是1，這樣很容易推知，長度為2的LIS最小末尾是3，于是可以把5淘汰掉，這時候B[1..2] = 1, 3，Len = 2

繼續，d[5] = 6，它在3後面，因為B[2] = 3, 而6在3後面，于是很容易可以推知B[3] = 6, 這時B[1..3] = 1, 3, 6，還是很容易了解吧？ Len = 3 了。

第6個, d[6] = 4，你看它在3和6之間，于是我們就可以把6替換掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len繼續等于3

第7個, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len變成4了

第8個, d[8] = 9，得到B[5] = 9，嗯。Len繼續增大，到5了。

最後一個, d[9] = 7，它在B[3] = 4和B[4] = 8之間，是以我們知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。

java代碼如下：

public static int findLongest(int[] A) {
		int n = A.length;
		int[] B = new int[n + 1];
		B[1] = A[0];
		int len = 1，index;
		for (int i = 1; i < n; i++) {
			if (A[i] > B[len]) {
				len++;
				B[len] = A[i];
			} else {
				index = search(1, len, B, A[i]);
				B[index] = A[i];
			}
		}
		return len;
	}
           

// 二分查找,查找第一個比他大的數
	public static int search(int start, int end, int[] a, int target) {
		int mid;
		while (start < end) {
			mid = (start + end) / 2;
			if (target >= a[mid])
				start = mid + 1;
			else
				end = mid;
		}
		return start;
	}
           

python代碼比較簡單，如下：

from bisect import bisect_left

def lengthOfLIS(nums: List[int]) -> int:
    dp = []
    for x in nums:
        if not dp or x > dp[-1]:
            dp.append(x)
        else:
            dp[bisect_left(dp, x)] = x
    return len(dp)
           

2.列印最長遞增子序列

方法一：列印第一個最長子序列O（n2） 

輸入例子:

7

89 256 78 1 46 78 8

數組array	ai	89	256	78	1	46	78	8
長度list	len(ai)	1	2	1	1	2	3	2

// 列印第一個最長序列
	public static ArrayList<Integer> maxSubIncreaseArray(int[] array) {
		int n = array.length;
		int[] list = new int[n];//存儲每個數結尾的最長串
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存儲所有遞增序列
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		int index = -1;// 用于标記目前元素之前的第一個遞增子序列的位置
		int maxIndex = 0;// 用于标記該序列的最長遞增子序列的位置
		int max = Integer.MIN_VALUE;// 最長遞增子序列的長度
		list[0] = 1;// 該清單用于标記包括目前元素在内的前半部分的最長遞增子序列的長度
		tmp.add(array[0]);
		res.add(tmp);
		for (int i = 1; i < n; i++) {
			index = -1;
			tmp = new ArrayList<Integer>();
			for (int j = 0; j < i; j++) {
				if (array[j] < array[i] && list[j]+1 > list[i]) {
					list[i] = list[j]+1;
					index = j;
				}
			}
			if (index > -1)
				tmp.addAll(res.get(index));
			tmp.add(array[i]);
			res.add(tmp);
			if (list[i] > max) {
				max = list[i];
				maxIndex = i;
			}
		}
		return res.get(maxIndex);
	}
           

方法二：列印最後一個最長字元串O(nlogn)，在求長度的方法上，與上述方法相結合

public static int findLongest(int[] A) {
		int n = A.length;
		int[] B = new int[n + 1];
		int[] C = new int[n + 1];//存儲i長的字元串位置
		C[1] = 1;
		B[1] = A[0];
		int len = 1, mid;

		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存儲所有遞增序列
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		int index = -1;// 用于标記目前元素之前的第一個遞增子序列的位置
		int maxIndex = 1;// 用于标記該序列的最長遞增子序列的位置
		int max = Integer.MIN_VALUE;// 最長遞增子序列的長度
		tmp.add(A[0]);
		res.add(new ArrayList<Integer>());
		res.add(tmp);

		for (int i = 1; i < n; i++) {
			tmp = new ArrayList<Integer>();
			if (A[i] > B[len]) {
				len++;
				B[len] = A[i];
				C[len] = i + 1;
				tmp.addAll(res.get(C[len - 1]));
				tmp.add(A[i]);
				if (len > max) {
					max = len;
					maxIndex = i + 1;
				}
			} else {

				index = search(1, len, B, A[i]);
				B[index] = A[i];
				while (index > 0 && B[index] >= A[i]) {
					index--;
				}
				if (index > 0) {
					tmp.addAll(res.get(C[index]));
					C[index + 1] = res.size();
				} else {
					C[1] = res.size();
				}
				tmp.add(A[i]);

			}
			res.add(tmp);
		}
		// 列印最後一個最長序列
		System.out.println(res.get(maxIndex));
		return len;
	}
           

3. 和最大的遞增子序列的和

// 和最大的遞增子序列
	public static long SubLongestAscendSum(int[] a) {
		int n = a.length;
		int f[] = new int[n];
		f[0] = a[0];
		long max = f[0];

		for (int i = 1; i < a.length; i++) {
			f[i] = a[i];
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i] && f[j] + a[i] > f[i]) {
					f[i] = f[j] + a[i];
					max = Math.max(f[i], max);
				}
			}
		}
		return max;
	}
           

4. 列印和最大的遞增子序列的和

// 列印和最大的遞增子序列
	public static List<Integer> SubLongestAscendSum2(int[] a) {
		int n = a.length;
		int f[] = new int[n];
		f[0] = a[0];
		long max = f[0];
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();// 存儲所有遞增序列
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		int index = -1;// 用于标記目前元素之前的第一個遞增子序列的位置
		int maxIndex = 0;// 用于标記該序列的最長遞增子序列的位置
		tmp.add(a[0]);
		res.add(tmp);

		for (int i = 1; i < a.length; i++) {
			f[i] = a[i];
			index = -1;
			tmp = new ArrayList<Integer>();
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i] && f[j] + a[i] > f[i]) {
					f[i] = f[j] + a[i];
					index = j;
				}
			}
			if (index > -1)
				tmp.addAll(res.get(index));
			tmp.add(a[i]);
			res.add(tmp);
			if (max < f[i]) {
				max = f[i];
				maxIndex = i;
			}
		}
		return res.get(maxIndex);
	}