给定一个无序的整数数组,找到其中最长上升子序列的长度, 注意,并没有连续的要求。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
方法:
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
1)动态规划。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLxkEVNFTWE9UMNpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLxMzNyIDOyYDMwETMxAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
思路同 找出数组的连续子数组的最大和, 滑雪问题中找出最长下坡路径,, 都是借助额外空间存储已经解出的结果。
#pragma once
#include <iostream>
#include <vector>
using namespace std;
class longestUpSubArray
{
public:
longestUpSubArray();
~longestUpSubArray();
public:
/*
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
*/
int lengthOfLIS(vector<int>& nums) {
if (nums.empty())
return 0;
int Num = nums.size();
if (1 == Num) {
return 1;
}
int resMaxLen = 1;
vector<int> totalResult(Num,1);//totalResult[i]表示以nums[i]结尾的最长升字串的长度.还是辅助记忆法@!
for (int endIdx = 1; endIdx < Num; endIdx++) {
int preIdx = 0;
int maxLenEndAtEndIdx = 1;
while (preIdx<endIdx) {
if (nums[endIdx] > nums[preIdx]) {
if (maxLenEndAtEndIdx < totalResult[preIdx] + 1) {
maxLenEndAtEndIdx = totalResult[preIdx] + 1;
}
}
preIdx++;
}
totalResult[endIdx] = maxLenEndAtEndIdx;
if (resMaxLen < maxLenEndAtEndIdx) {
resMaxLen = maxLenEndAtEndIdx;
}
}
return resMaxLen;
}
void Test() {
//vector<int> nums = { 10,9,2,5,3,7,101,18 };
vector<int> nums = { 2,5,3,4 };
int len = lengthOfLIS(nums);
cout << "len=" << len << endl;
}
};
int main() {
longestUpSubArray obj;
obj.Test();
}