【算法】合唱队形问题&最大上升子序列详细代码＋分析（C++）-创新互联

于是得到了答案：

问题①：给数组内所有元素赋值为1是为了防止出现如2 5 1这样的排列的时候到了第三个同学高度为1 则此时大上升子序列的值应该为1，如果不整体赋初值的话，到第三个同学这里，上升序列的长度就是0了

但是这好像仍然不能解决问题②，于是我研究了下这个循环

这里使用了循环for(int j=1;j

a[3] = 5 >a[4] = 3 导致f[4] = 1

而使用循环会保证和前面所有的上升子串都进行了一次比较

j=1:a[1]< a[4] = 3 -->f[4] = f1[1] + 1 = 2

表示序列f1[1] + 第4个同学可以组成新序列1 3且长度为2

j=2:a[2]< a[4] = 3 -->f[4] = f1[2] + 1 = 3

表示序列f2[1] + 第4个同学可以组成新序列1 2 3且长度为3

j=1:a[3] >a[4] = 3 -->f[4] = f1[2] = 3

5 >3 则第三个序列f[3]无法和第4个同学组成新序列 序列长度还是之前的3

得出序列f[4]大值为3

所以for(int j=1;j

f1[j]代表到第j个同学的大上升子串 则为了求集合大值 使用了一次循环遍历

如果a[i] >a[j]说明第i个同学要比第j个同学 和第j个同学已经建立起的上升子序列中所有同学都高，则上升子序列的大值，就可以更新为已经建立的上升子序列f1[j]加上同学a[i] 表示为f1[j] + 1

#includeusing namespace std;
int n,a[3001],f1[3001],f2[3001],MAX;//f1[i]表示上升子序列的个数 f2[i]表示反方向开始的上升子序列的个数


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//下标从1开始
    {
        cin>>a[i];
        f1[i] = 1;//这里很关键 递归边界是f[1] = 1 以及每个上升子序列的最小值为1
        //但是给数组内所有元素赋值为1是为了防止出现如2 5 1这样的排列的时候
        //到了第三个同学高度为1 则此时大上升子序列的值应该为1
        for(int j=1;ja[4] = 3 导致f[4] = 1
            //而使用循环会保证和前面所有的上升子串都进行了一次比较
            //j=1:a[1]< a[4] = 3 -->f[4] = f1[1] + 1 = 2
            //表示序列f1[1] + 第4个同学可以组成新序列1 3且长度为2
            //j=2:a[2]< a[4] = 3 -->f[4] = f1[2] + 1 = 3
            //表示序列f2[1] + 第4个同学可以组成新序列1 2 3且长度为3
            //j=1:a[3] >a[4] = 3 -->f[4] = f1[2] = 3
            //5 >3 则第三个序列f[3]无法和第4个同学组成新序列 序列长度还是之前的3
            //得出序列f[4]大值为3
        }
    }

    for(int i=n;i>=1;i--)
    {
        f2[i] = 1;
        for(int j=n;j>i;j--)
        {
            if(a[j]

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧