|
目录
1.最长上升递增子序列
2.最长上升递增的子序列
1.最长上升递增子序列
? ? ? ?题目：674. 最长连续递增序列
? ? ? ?方法：动态规划?
? ? ? ?定义dp数组 dp[i]是以i结尾的最长递增子序列
? ? ? ?dp[0]=1
? ? ? ?dp[i]=dp[i-1]+1? ?arr[i]>arr[i-1]
? ? ? ?dp[i]=1? ? ? ? ? ? ? arr[i]<arr[i-1]
? ? ? ?num=max(dp[i]) 0<=i<=n
? ? ? ? 时间复杂度O(n) 空间复杂度O(n)?
? ? ? ? 优化可以dp[i]只依赖于dp[i-1],可以使用临时变量存储，空间复杂度O(1)
代码如下?
//674. 最长连续递增序列
// nums = [1,3,5,4,7]
//674. 最长连续递增序列
//定义dp数组
//dp[i]:以i结尾的最长递增子序列
//dp[i]=dp[i-1]+1 arr[i]>arr[i-1]
//dp[i]=1 arr[i]<arr[i-1]
//num=max(dp[i]) 0<=i<=n
//时间复杂度O(n) 空间复杂度O(n)
public static int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = 1;
}
max = Math.max(max, dp[i]);
}
return max;
}
//递归方程只利用前一个的元素，可以使用一个变量存储值
//时间复杂度O(n),空间复杂度O(1)
public static int findLengthOfLCIS2(int[] nums) {
int preNum = 1;
int max = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
preNum = preNum + 1;
} else {
preNum = 1;
}
max = Math.max(max, preNum);
}
return max;
}
2.最长上升递增的子序列
? ? ? ? 题目：300. 最长递增子序列
? ? ? ? 方法：
????????1.动态规划??
? ? ? ? 2.二分查找
? ? ? ? 动态规划
? ??????dp[i]是以i结尾的最长递增子序列
? ??????dp[i]=max(dp[j])+1 arr[j]<arr[i]? ?0<=j<i
? ??????dp[0]=1
? ??????max=map(dp[i]) ? ?0<=i<=n
? ??????时间复杂福O(n^2) 空间复杂度O(1)
? ? ? ? 二分查找
? ? ? ?遍历数组中的每一个元素，使用二分查找，插入数组中。
//300. 最长递增子序列
//10,9,2,5,3,7,101,18
//dp[i] 以i结尾的最长递增子序列
//dp[i]=max(dp[j])+1 arr[j]<arr[i]
//dp[0]=1
//max=map(dp[i]) 0<=i<=n
//时间复杂福O(n^2) 空间复杂度O(1)
public static int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for (int i = 1; i < dp.length; i++) {
//先对i值进行初始化为1
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
/**
* @param
* @Description: 使用二分查找解决最大上升子序列问题
* @Date: 2020/2/5 10:34
* @Author: fuguowen
* @Return
* @Throws
*/
//时间复杂度O(nlog(n))
//把上升的递增子序列存储在一个数组中，每次二分查找，如果不是大于最大最或者小于最小值，数组的首尾新增元素
//如果是中间的元素替换对应的元素
public static int lengthOfLIS2(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
//把递增的上升子序列存在一个数组中
List<Integer> list = new ArrayList<>();
list.add(nums[0]);
for (int i = 1; i < nums.length; i++) {
int[] arr = list.stream().mapToInt(Integer::valueOf).toArray();
int num = binarySort(arr, nums[i]);
//比所有的数都大
if (num == list.size()) {
list.add(nums[i]);
//比所有的数都小
} else if (num == 0) {
list.set(0, nums[i]);
} else {
//覆盖对应的值
list.set(num, nums[i]);
}
}
//最后返回对应的最长子序列的个数
return list.size();
}
/**
* @Description: 二分查找
* @Date: 2020/2/5 10:32
* @Author: fuguowen
* @Return 二分查找, 如果值存在返回对应的索引，如果值不存在，返回比当前值大的下一个元素的索引
* @Throws
*/
public static int binarySort(int[] array, int key) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (key < array[mid]) {
high = mid - 1;
} else if (key > array[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return low;
}
|