求序列里最长的非降序列例如：输入：{5,3,4,8,6,

[问答题]

求序列里最长的非降序列例如：输入：{5,3,4,8,6,7} 输出：4 即{3,4,6,7}

sherluck

#include<iostream>

#include<vector>

usingnamespacestd;

intlongest(inta[],intn){

vector<int> dp(n,1); //dp[i]表示 0-i的最大子序列长度

for(inti=0;i<n;i++){

for(intj=i-1;j>=0;j--)

if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);

}

returndp[n-1];

}

intmain(){

intn;

cin>>n;

inta[n];

for(inti=0;i<n;i++)

cin>>a[i];

cout<<longest(a,n);

发表于 2017-08-29 22:48:55 回复(0)

Russel

#include <stdio.h>
#include <algorithm>

using namespace std;

int solve(int *A, int n)
{
   int loc[n];
   int glo;
   loc[0] = glo = 1;
   for (int i = 1; i < n; i++)
   {
       int ma = 1;
       for (j = i-1; j >= 0; j--) 
       {
           if (A[i] >= A[j])
               ma = max(ma, loc[j]);
       }
       loc[i] = ma + 1;
       glo = max(glo, loc[i]);
    }
    return glo;
}

int main()
{
    int n;
    int a[n];
    //输入啊a[n]
    printf("最长非降序列长度为： %d\n", solve(a, n));
    return 0;
}

发表于 2016-06-17 17:32:21 回复(0)

手机用户3091285952

#include <stdio.h>
void Update(int * B,int len,int d) {
    while(len>1) {
        if ( d>=B[len-1] ) {
            B[len] = d;
            return ;
        }
        --len;
    }
    B[1] = d;
}

int LIS(int d[], int n) {
    int * B = new int[n+1];
    memset(B,0x7fffffff,(n+1)*sizeof(int));
    B[1] = d[0];
    int len = 1;
    for ( int i=1;i<n;++i ) {
        if ( d[i]<B[len] ) {
            Update(B,len,d[i]);
        }
        else {
            B[++len] = d[i];
        }
    }
    return len;
}

int main() {
    int d[6] = {5,3,4,8,6,7};
    printf("%d\n",LIS(d,6));
    return 0;
}

发表于 2015-05-13 17:22:08 回复(0)

青杉

为啥是两个循环呢。。不是就一个么？相邻两条数据比较啊

int[] array={5,3,4,8,6,7};

int count=0;

List list = new ArrayList();

for(int i=0;i<array.length;i++){

if(array[i]<array[i+1]){

count++;

list.add(array[i]);

}

int[] res= (int[])list.toArray(new int[list .size]);

然后输出应该就是吧。。

发表于 2015-04-24 11:17:14 回复(1)

鸡立鹤群

我自己想的是用最笨的方法，类似于动态规划，不断的由短的凝聚起来。即3，4，6，7肯定是3，4，6与3，4，7凝聚起来的，按照这种想法不断凝聚就一定是最长的

发表于 2015-04-20 21:32:27 回复(0)

慈慈乱了

#include <iostream>
using namespace std;

int main()
{
int array[6]={5,3,4,8,6,7};
    int subarray[6]={0};
    int sum=0;
    subarray[0]=5;
    for (int i=0;i<6-1;i++)
    {
        if (array[i+1]>array[i])
        {
            subarray[sum++]=array[i+1];
        }
        else
        {
            if (sum!=0)
            {
                if (array[i+1]<subarray[sum-1])
                {
                    subarray[sum-1]=array[i+1];
                }
            }
            else
            {
                if (array[i+1]<subarray[sum])
                {
                    subarray[sum++]=array[i+1];
                }
            }

        }
    }
    for (int i=0;i<sum;i++)
    {
        cout<<subarray[i]<<endl;
    }
    return 0;
}

发表于 2015-04-20 19:11:01 回复(0)