最长上升子序列
给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
此题在审题的时候就要注意一下子串和子序列的区别。子串必须是连续的，但是子序列只要是有左右顺序即可，可以不需要是连续的。
给出的数据是个数，以及一支长串字符序列，要求返回的是最长递增序列的长度。
状态表示：f[i] 表示的是以第i个字符结尾的从1-i的最长上升子序列的长度。
状态属性：max
base case：f[i] = 1 ; 因为每一个字符可以看作是只有一个字符的序列
状态转移：对于每一个f[i] 他的值其实来源于他前面的序列中比他小的f[j] 集合中最大的然后在加上一
//表示的是大概意思，代码是不对的，但是思路是这样的
for(int i = 1 ; i <= n ; ++i)
{
for(int j = i-1 ; j >= 0 ; --j)
{
if(a[i] > a[j])
{
f[i] = f[j]+1 ;
}
res = max(res, f[i]) ;
}
}
So,代码如下：
#include
using namespace std ;
const int N = 1010 ;
int a[N] , f[N] ;
int main()
{
int n ;
cin >> n ;
int res = -1e9-1 ;
for(int i = 1 ; i <= n ; ++i)
{
cin >> a[i] ;
}
for(int i = 1 ; i <= n ; ++i)
{
f[i] = 1;
for(int j = i-1 ; j >= 0 ; --j)
{
if(a[i] > a[j])
{
f[i] = max(f[i] , f[j] + 1) ;
}
}
res = max(res , f[i]) ;
}
cout << res << endl ;
return 0 ;
}
ok，分析一下上面代码的时间复杂度O(n2) 。
那么是否存在更加优化时间的方案呢？
贪心加二分
我们想到其实对于f[i]表示的是以a[i]结尾的子序列来说，我们可以有这样的想法：
1.首先明确一点：我们维护一个上升子序列，想让子序列的长度更长，那就相当于往后遍历的时候遇到了比已经维护的子序列中最大的要小的数字a[i]的时候，我们应该找子序列中小于a[i]的最大的数字，然后将其替换成a[i] 。这样就可以保证之后理论上可以替换更多的数字，从而维护了最长的子序列。
2.那么我们如果仅仅是两轮循环遍历，来实现上述思想，那么细心的同学就可以发现，时间复杂度并没有优化，只是思路发生了变化而已。所以，可以这样实现的重点就是我们在维护的子序列中可以采用二分的方法来找到小于a[i]的最大数字。所以时间复杂度优化为O(nlgn).
actually，这种思路的话，其实个人感觉不太像dp，而是更像是贪心算法，在加上二分。
ok，下面是代码实现：
#include
using namespace std ;
const int N = 100010 ;
//q[N]是我们要维护的序列
//w[N]负责读入数据
int q[N] , w[N] ;
int cnt ;
int find(int *q , int num)
{
int l = 1 ;
int r = cnt ;
while(l < r)
{
int mid = l + r >> 1 ;
if(q[mid] < num)
{
l = mid + 1 ;
}
else
{
r = mid ;
}
}
return l ;
}
int main()
{
int n ;
cin >> n ;
for(int i = 1 ; i <= n ;++i)
{
cin >> w[i] ;
}
q[++cnt] = w[1] ;
for(int i = 2 ; i <= n ;++i)
{
if(w[i] > q[cnt])
{
q[++cnt] = w[i] ; //如果是个比维护序列的最大值大的，就直接加入即可
}
else
{
int t = find(q , w[i]) ;
q[t] = w[i] ;
}
}
cout << cnt << endl ;
return 0 ;
}
ok,以上是解决了长度的问题，那我们开始举一反三，是否可以在举一个同类的问题
能否返回所有长度为最长的上升子序列的个数？
好吧，今天时间有限，等下次在更…….
—————————————————————————–2021.11.6更新————————————————————————————-
如何才能返回所有长度为最长的上升子序列长度的个数呢，我们先来看一下leetcode里面的一道题
673. 最长递增子序列的个数 - 力扣（LeetCode） (leetcode-cn.com)
可以看出来，与单纯的求最长递增子序列相比，该题多了一维信息，那就是收集f[i] == ans的f[i]的个数。可以看成是二维的LIS问题。
那么我们怎么进行g[i] (以nums[i] 为结尾的最长子序列的个数)的更新呢？
逻辑分析
状态表示：g[i] 表示以nums[i] 结尾的同时是最长递增子序列的个数
状态属性：max
base case：g[i] = 1 ;
状态转移：在对f数组进行更新的时候，我们考虑到f[i] = max(f[i] , f[j] + 1) ，这表示着f的状态的两个来源，
我们分成三个情况来讨论：
一：f[i] > f[j] + 1 表示不需要用这个j来进行更新，也就是说，不会发生任何事情，所以我们在代码中可以直接省略
二：f[i] == f[j] + 1 表示在i之前还存在一种情况可以在i的序号下得到最长子序列，例如：1223 ，以3为结尾就会有两个。我们可以直接g[i] += g[j] 即可。
三：f[i] < f[j] + 1 表示可以用j来进行更新当前的数组，那就是g[i] = g[j] 即可。
//用代码表示转移方程就是这样的
for(int i = 0 ; i < n ; ++ i)
{
f[i] = g[i] = 1 ;
for(int j = 0 ; j < i; ++ j)
{
if(nums[i] > nums[j])
{
if(f[i] == f[j] + 1)
{
g[i] += g[j] ;
}
else if(f[i] < f[j] + 1)
{
g[i] = g[j] ;
f[i] = f[j] + 1 ;
}
}
}
}
Talk is cheap ,Show me your code!!!
同时更新版本
class Solution {
public:
int findNumberOfLIS(vector& nums) {
int res = 0 ,ans = 0 ;
int n = nums.size() ;
vector f(n) , g(n) ;
for(int i = 0; i < n ; ++ i)
{
f[i] = g[i] = 1 ;
for(int j = 0 ; j < i ; ++ j)
{
if(nums[i] > nums[j])
{
if(f[i] == f[j] + 1)
{
g[i] += g[j] ;
}
else if(f[i] < f[j] + 1)
{
g[i] = g[j] ;
f[i] = f[j] + 1 ;
}
}
}
ans = max(ans , f[i]) ;
}
for(int i = 0 ; i < n ; ++ i)
{
if(f[i] == ans)
{
res += g[i] ;
}
}
return res ;
}
};
ok,这是同时更新f,g的版本。我们还可以将f与g独立处理.
独立处理版本
class Solution {
public:
int ans = 0 ,res = 0 ;
int findNumberOfLIS(vector& nums) {
int n = nums.size() ;
vector f(n) , g(n) ;
for(int i = 0 ; i < n ; ++ i)
{
f[i] = 1 ;
for(int j = 0 ; j < i ; ++ j)
{
if(nums[i] > nums[j])
f[i] = max(f[i] , f[j] + 1) ;
}
ans = max(ans , f[i]) ;
}
for(int i = 0 ; i < n ; ++ i)
{
if(f[i] == 1) g[i] = 1 ;
for(int j = 0 ; j < i ; ++ j)
{
if(f[i] == f[j] + 1 && nums[i] > nums[j])
g[i] += g[j] ;
}
}
for(int i = 0 ; i < n ; ++ i)
{
if(f[i] == ans)
res += g[i] ;
}
return res ;
}
};
意思要比同时更新要更加好理解，先按部就班的将f数组完成，对于g数组来说，只要f[i] 是由可以有f[j] 来更新到的，他就会把所有的可能都加进去，前提是g[i] 一开始是空的，如果初始化为1的话，结果会有错。最后，只要查找哪些f是最大的，然后res一直加上g就可以了。
所以为什么要说这个呢?
是为了引出下面这一道题，他是上面的题目的变种，需要稍加考虑一下细节。
ok，我们再来看看这一道题。
低买
给定一段时间内股票的每日售价（正 16 位整数）。
你可以选择在任何一天购买股票。
每次你选择购买时，当前的股票价格必须严格低于你之前购买股票时的价格。
编写一个程序，确定你应该在哪些天购进股票，可以使得你能够购买股票的次数最大化。
例如，下面是一个股票价格时间表：
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87
如果每次购买都必须遵循当前股票价格严格低于之前购买股票时的价格，那么投资者最多可以购买四次该股票。
买进方案之一为：
Day 2 5 6 10
Price 69 68 64 62
输入格式
第 1 行包含整数 N，表示给出的股票价格的天数。
第 2 至最后一行，共包含 N 个整数，每行 10 个，最后一行可能不够 10 个，表示 N 天的股票价格。
同一行数之间用空格隔开。
输出格式
输出占一行，包含两个整数，分别表示最大买进股票次数以及可以达到最大买进次数的方案数。
如果两种方案的买入日序列不同，但是价格序列相同，则认为这是相同的方案（只计算一次）。
数据范围
1≤N≤5000
输入样例1：
12
68 69 54 64 68 64 70 67 78 62
98 87
输出样例1：
4 2
输入样例2：
5
4 3 2 1 1
输出样例2：
4 1
逻辑思路
题目意思比较直白，就是LDS(最长下降子序列) ,但是要注意点是，位置不同但是数字相同的只能算一种。
例如1223 res == 1,而不是res==2 。
那我们如何来考虑呢？
我们先用独立处理的方式来进行分析，f的算法是不会变得。那么对于，g数组其实就是在从左往右的顺序的时候，当f[i] == f[j] && nums[i] == nums[j] ，的时候需要特判一下，这就相当于是到第三位的时候是2，此时f[3] == 2 f[2] == 2 ，并且nums[2] == nums[3] == 2 ，所以我们需要将此时的g，变成0，反正就是只要加上一个就行了，随便你是g[i] =0 , 还是g[j] = 0 这样，我们在最后一次循环得出res的时候，只会加一次。
ok，这就是大致思路，下面贴个代码。
独立处理做法
#include
using namespace std ;
const int N = 5010 ;
int nums[N] , f[N] , g[N] ;
int n ;
int res = 0 ,ans = 0 ;
int main()
{
cin >> n ;
for(int i = 1; i <= n ; ++ i)
{
cin >> nums[i] ;
}
for(int i = 1 ; i <= n ; ++ i)
{
f[i] = 1;
for(int j = 1 ; j < i ; ++ j)
{
if(nums[i] < nums[j])
f[i] = max(f[i] , f[j] + 1) ;
}
ans = max(ans , f[i]) ;
}
for(int i = 1 ; i <= n ; ++ i)
{
if(f[i] == 1) g[i] = 1;
for(int j = 1 ; j < i ; ++ j)
{
if(f[i] == f[j] + 1 && nums[i] < nums[j])
g[i] += g[j] ;
else if(f[i] == f[j] && nums[i] == nums[j])
g[j] = 0 ;
}
}
for(int i = 1 ; i <= n ; ++ i)
{
if(f[i] == ans)
res += g[i] ;
}
cout << ans << " "<< res << endl ;
return 0 ;
}
那我们用同步更新的思路来再想一遍
对于f来说，依然是没有什么影响。此时，对于g来说，一种从源头根治的方法是，每次j来进行搜索的时候，都将在确立了f之后，将之前的相同元素的f变为另一个很小的数。
同步更新思路：
贴个代码：
#include
using namespace std ;
const int N = 5010 ;
int nums[N] , f[N] , g[N] ;
int n ;
int res = 0 ,ans = 0 ;
int main()
{
cin >> n ;
for(int i = 1; i <= n ; ++ i)
{
cin >> nums[i] ;
}
for(int i = 1 ; i <= n ; ++ i)
{
f[i] = 1 ;
for(int j = 1 ; j < i ; ++ j)
{
if(nums[j] > nums[i])
f[i] = max(f[i] , f[j] + 1) ;
}
if(f[i] == 1) g[i] = 1 ;
ans = max(ans , f[i]) ;
for(int j = 1 ; j < i ; ++ j)
{
if(nums[j] == nums[i])
f[j] = -1 ;
}
for(int j = 1 ; j < i ; ++ j)
{
if(nums[j] > nums[i] && f[i] == f[j] + 1)
g[i] += g[j] ;
}
}
for(int i = 1 ; i <= n ; ++ i)
{
if(f[i] == ans)
{
res += g[i] ;
}
}
cout << ans << " "<< res << endl ;
return 0 ;
}
其实还有一个有意思的地方是在于，不同方法的时候，g的预处理的值也是比较有意思的。
总结一下，独立处理意思容易理解，但是代码相对来说比较冗余。同时更新理解起来稍微难一些，但是代码要简洁。
好了，说完了，拜拜 >_< .
