C++ 最长摆动子序列（动态规划求解）

最长摆动子序列（Longest Wiggle Subsequence）是指给定一个序列，从其中选出一些元素组成最长的摆动子序列。该子序列中任意相邻两个元素的差值交替为正或负（不能为0），并且求得的子序列的长度要尽可能地长。

例如，序列[1, 7, 4, 9, 2, 5]的最长摆动子序列可以是[1, 7, 4, 9, 2, 5]、[1, 7, 4, 9, 2]或者[1, 7, 4, 9, 5]，它们都是符合要求的摆动子序列，而最长的子序列长度为6。

解决这个问题可以采用动态规划思想。定义两个数组up和down，分别表示以当前元素为末尾的最长上升子序列和最长下降子序列的长度。初始时，每个元素的up和down都为1。

接着遍历整个序列，对于每个位置i，分别计算其与前面元素的差值diff。如果diff大于0，则表明i比前面的元素大，可以将i加入到最长下降子序列中，则有：up[i] = down[i-1]+1，down[i]不变；如果diff小于0，则表明i比前面的元素小，可以将i加入到最长上升子序列中，则有：down[i] = up[i-1]+1，up[i]不变；否则diff等于0，跳过本次循环。

最后取up和down两个数组中的最大值即为所求最长摆动子序列的长度。

如下c++代码实现：

//c++ 动态规划求解最长摆动子序列
#include "iostream"
#include "algorithm"
using namespace std;

//求解最长摆动子序列
int wiggleMaxLength(int *a,int n)
{
//    如果只有两个元素，那么大小就是n
    if(n<=1)
    {
        return n;
    }
//    up表示当前为末尾的最长摆动子序列的长度
    int up[n];
//    down表示当前为末尾的最长摆动子序列的长度
    int down[n];
//    初始化长度为1
    up[0]=1;
    down[0]=1;
// 遍历计算
    for (int i = 1; i < n; ++i) {
//        如果当前这个数比前一个数要大，就表示上升，为负。
        if(a[i]>a[i-1])
        {
//            向上为前一个加1
            up[i]=down[i-1]+1;
//            下降不变
            down[i]=down[i-1];
        }
//        相反
        else if (a[i]<a[i-1])
        {
            down[i]=up[i-1]+1;
            up[i]=up[i-1];
        }
//        如果前一个数字和当前的这个数字的差值为0，up和down的数值不变
        else
        {
            down[i]=down[i-1];
            up[i]=up[i-1];
        }
    }
//    返回最大的就是最长摆动子序列了。
    return down[n-1]>up[n-1] ? down[n-1]:up[n-1];
}

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

//    开始求解最长摆动子序列的长度
    cout<<wiggleMaxLength(a,n)<<endl;
}