300 Longest Increasing Subsequence
Reference: https://leetcode.com/problems/longest-increasing-subsequence/solution/
Method 1: Brute Force 暴力找到
public class Solution {
public int lengthOfLIS(int[] nums) {
return lengthofLIS(nums, Integer.MIN_VALUE, 0);
}
public int lengthofLIS(int[] nums, int prev, int curpos) {
if (curpos == nums.length) {
return 0;
}
int taken = 0;
if (nums[curpos] > prev) {
taken = 1 + lengthofLIS(nums, nums[curpos], curpos + 1);
}
int nottaken = lengthofLIS(nums, prev, curpos + 1);
return Math.max(taken, nottaken);
}
}Method 2: Recursion with Memoization