我要招人

去企业版

首页 > 试题广场 >

求序列里最长的非降序列例如：输入：{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)

jamweak

一次for循环遍历输入序列A，如果A[i+1]>A[i]，则将A[i+1]加入到所求非降序列的最后；

如果A[i+1]<A[i]，则将A[i+1]和所求非降序列的最后一个元素进行比较，该位置保留这两者之间较小的元素。

根据上面的输入：所求非降序列的过程为:

3,4

3,4,8

3,4,6

3,4,6,7 遍历结束。

发表于 2015-04-20 17:20:58 回复(2)

小屁孩Bear

2个for循环

第一个从后往前，

第二个从自己到最后面，不断更新自己到最后面的最大距离

发表于 2015-04-19 17:19:51 回复(0)

幽兰生于暮色

用两个for循环，不断更新最大的长度

发表于 2015-04-19 10:22:03 回复(0)

提交观点

问题信息

贪心百度

上传者：佳晨

难度：

9条回答 11收藏 12359浏览

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

问题信息

热门推荐

相关试题

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

问题信息

热门推荐

相关试题

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