給定一個整數(shù)數(shù)組（下標(biāo)從 0 到 n-1槽华， n 表示整個數(shù)組的規(guī)模）征候，請找出該數(shù)組中的最長上升連續(xù)子序列杭攻。（最長上升連續(xù)子序列可以定義為從右到左或從左到右的序列。）
樣例
給定 [5, 4, 2, 1, 3], 其最長上升連續(xù)子序列（LICS）為 [5, 4, 2, 1], 返回 4.
給定 [5, 1, 2, 3, 4], 其最長上升連續(xù)子序列（LICS）為 [1, 2, 3, 4], 返回 4.
思路：兩邊遍歷疤坝，利用動態(tài)規(guī)劃思路兆解，每當(dāng)找到一個子序列比上一次找到的大，就存儲當(dāng)前的子序列跑揉，注意最后遍歷結(jié)束的時候還要比較一次锅睛，因為一般寫的程序是發(fā)現(xiàn)下降的時候來檢查上升序列是否是最大的埠巨，如果序列本身在最后沒有下降，不檢查肯定是不合理的现拒，一開始就錯在這里了辣垒，到vs里調(diào)試了一下看了每步的結(jié)果才弄對，兩次遍歷：
code：
int longestIncreasingContinuousSubsequence(vector<int> &A) {
int num_up=0;
int num_down=0;
int num_max[2]={0};
if(A.empty())
return 0;
if(A.size()==1)
return 1;
for(int i=1;i<A.size();i++) //一遍遍歷
{
if(A[i]>=A[i-1])
num_up++;
if(A[i]<A[i-1])
{
if(num_up>num_max[0])
num_max[0]=num_up; //如果比上一次存的大印蔬，就賦值給最大值
num_up=0; //這個清零
}
}
if(num_up>num_max[0])
num_max[0]=num_up;
//上面這個if很重要勋桶，因為可能結(jié)尾之前一直上升，我們前面的程序是在下降的時候才檢查這次的
//上升值是否比以前存的大侥猬，但是可能一直沒有下降就不檢查了么例驹？所以跳出循環(huán)以后這里還是要檢查一次
for(int i=A.size()-2;i>=0;i--) //一遍遍歷
{
if(A[i]>=A[i+1])
num_down++;
if(A[i]<A[i+1])
{
if(num_down>num_max[1])
num_max[1]=num_down;
num_down=0;
}
}
if(num_down>num_max[1])
num_max[1]=num_down;
return (num_max[0]>num_max[1])?num_max[0]+1:num_max[1]+1;
// write your code here
}
over
