要写一个程序，求一个整数序列中，非递增的个数。
输入：7 300 275 215 245 198 150 235
输出：5

设数列为A
f[i] = sigma(f[j]) (满足A[i]>=A[j], i<j)

ans = sigma(f[i]-1)

这个输出有问题吧？怎么看都不对

为什么是5呢，楼主可否结束一下，非递增的话，我怎么看应该是4啊~

楼主的意思可能是这样的

首先找出最长的递增数列

非递增的个数 就是不在此数列中的数

是吗

#include<stdio.h>
int a[]={7,300,275,215,245,198,150,235};
int b[20];//存放以a[i](0<=i<=a.length-1)为最后元素的最大递增子串的长度。
int num = 10;//num为a数组的长度
int k;//存放最大递增子串最后一个元素的下标

//求出b[i]中最大的值，并将其下标存在k中
int Max() {
    int temp = 0;
    for (int i = 0; i < num; i++) {
        if (b[i] > temp) {
            temp = b[i];
            k = i;
        }
    }
    return temp;
}

// 以a[i](0<=i<=a.length-1)为最后元素的最大递增子串的长度存到b[i]中
int Lis() {
    b[0] = 1;//以a[0]为最后元素的子串只有a[0]，所以长度为1.
    int k;
    for (int i = 1; i < num; i++) {
        k = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i] && k < b[j]) {
            //比较所有小于a[i]并位于a[i]前面的最大子串的长度。比如3 6 4 5，那么以5结尾的最大子串长度
            //等于：max{(小于5的元素有3,4)3的最大子串长度，4的最大子串长度}+1;
                k = b[j];
            }
        }
        b[i] = k + 1;//max{(小于5的元素有3,4)3的最大子串长度，4的最大子串长度}+1;
    }
    return Max();
}



void main(){
    printf("最大递增子串的长度为：%d\n",Lis());
    printf("非递增个数：%d\n",8-Lis());
   
}

可能意思没有表达清除，题目要求是任意输入一个数列，比如给的例子，输入7个数，分别为所示。非递增顺序的有300 275 215 198 150 个数为5，也就是说整数个数预先不知道。也就没有先定义如下：int a[]={7,300,275,215,245,198,150,235}。数列的个数是可以改变的，所以就想不清楚如何把要输入的整数存起来。

呵呵
其实你说的还是不清楚。。。。。。。。。。。。。。。。。
#define n 30        你想输入多少个数改下30不就OK了

int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);

非递增数列有很多，你是要输出最长的吗。。。。。


给你写了个，上机通过。。。。。注意    它输出的时候是从小到大输出的


#include<stdio.h>
#define NUM 10
int a[NUM];


int b[NUM];//存放以a[i](0<=i<=a.length-1)为最后元素的最大非递增子串的长度。
 
int k;//存放最大非递增子串最后一个元素的下标

//求出b[i]中最大的值（即是最大非递增子串的长度），并将其下标存在k中
int Max() {
    int temp = 0;
    for (int i = 0; i < NUM; i++) {
        if (b[i] > temp) {
            temp = b[i];
            k = i;
        }
    }
    return temp;
}

// 以a[i](0<=i<=a.length-1)为最后元素的最大非递增子串的长度存到b[i]中
int Lis() {
    b[0] = 1;//以a[0]为最后元素的子串只有a[0]，所以长度为1.
    int k;
    for (int i = 1; i < NUM; i++) {
        k = 0;
        for (int j = 0; j < i; j++) {
            if (a[j] >= a[i] && k < b[j]) {
            //比较所有大于a[i]并位于a[i]前面的最大子串的长度
            
                k = b[j];
            }
        }
        b[i] = k + 1;
    }
    return Max();
}

//从小到大输出非递增子串
void print(int index){
    printf("%d ",a[index]);  
    for (int i = 0; i < index; i++) {
        if (b[i] == b[index] - 1 && a[i] >= a[index]) {
            print(i);
            break;
        }
    }
}

void main(){

for(int i = 0; i < NUM; i++)

scanf("%d",&a[i]);


    printf("最大非递增子串的长度为：%d\n",Lis());
    printf("最大递增子串从小到大输出为：\n");
    print(k);
}








[ 本帖最后由 encounter 于 2010-8-30 21:59 编辑 ]

题目的要求是：个数是输入的，而不是预先定义的。

小妹妹，
学习要学会变通呀

没有万能的程序。。。。
你把NUM的值改大一点不就行了吗
不过那样会出现很多0
最后的结果的自己辨别下
难道连数一下，10改成100，都闲麻烦吗
21实际还没有那么智能
至少还得要程序员输入数据。。。。。