Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4
虽然思路不难,但是store[i]的更新很容易写错
public class Solution { public int longestIncreasingSubsequence(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] store = new int[nums.length]; store[0] = 1; int res = 1; for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] <= nums[i]){ store[i] = Math.max(store[j], store[i]); } } store[i]++; res = Math.max(res, store[i]); } return res; } }