2017sjtu-ZIG-ZAG

题意理解：在输入的数组中，找到所有的增-减-增...或减-增-减...子序列中最长的子序列长度。

思路：很经典的单串问题，考虑第i个位置必选的情况，且第i个位置的dp值与0~i-1均有关。 但是本题又有两种状态，所以考虑开一个dp[n][2]数组，分别存储两种情况。

本题和leetcode：

1567链接

122链接

309链接

有相似之处，均为二维dp分别表示两种状态的值。

本题：

状态表示：

dp[i][0]表示以i为结尾，且是增加到i的所有子序列的集合，属性为子序列长度的最大值

dp[i][1]表示以i为结尾，且是减少到i的所有子序列的集合，属性为子序列长度的最大值

状态转移：

#include <iostream>
#include <algorithm>
using namespace std;
const int N=55;

//dp[i][0]表示以i为结尾，且是增加到i的子序列
//dp[i][1]表示以i为结尾，且是减少到i的子序列
int dp[N][2];
int n;
int num[N];

int main()
{
    while(cin>>n)
    {
        for(int i=0;i<n;i++) cin>>num[i];

        if(n==1)//若数组长度为1，则直接进入下一次循环
        {
            cout<<1<<endl;
            continue;
        }


        int ans=0;
        for(int i=0;i<n;i++){
            dp[i][0]=dp[i][1]=1;//初始化，表示每个数都可以作为一个长度为1的子序列
            for(int j=0;j<i;j++)//枚举0~i-1
            {   //枚举0~i-1，并实现状态转移
                if(num[i]>num[j]) dp[i][0]=max(dp[i][0],dp[j][1]+1);
                if(num[i]<num[j]) dp[i][1]=max(dp[i][1],dp[j][0]+1);
            }
            ans=max(ans,max(dp[i][0],dp[i][1]));//实时更新最长长度
            }

        cout<<ans<<endl;
    }
    return 0;
}

参考大佬链接：

惊喜：链接leetcode376原题