编程问题，求算法
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87
要求
随便那天做为开始都可以,怎么样才能找出以这天为开始,
然后你找到的Price必须比前一天的小,这样的day越多?


在线等答案。。。。。。。

[解决办法]
这是最简单的动态规划题.属于求(最大不下降子序列> 问题的变型题.
解法都是一样,推动动态规划的递推转移方程即可.
本题只是求最长的天数,所以不用存路径,求解时简单得多.
需要相关知识可以上网搜一下(最大不下降子序列> 即可.

以下是本题的解题代码(dev-cpp编译运行通过):
#include <stdio.h>

int price[5001];
int length[5001];
int n, maxn;

int main()
{
int i, j;
scanf( "%d ", &n);
for (i=0; i <n; ++i)
scanf( "%d ", &price[i]);
maxn = 1;
length[0] = 1;
for (i=1; i <n; ++i)
{
length[i] = 0;
for (j=0; j <i; ++j)
if (price[i] <price[j] && length[i] <length[j])
length[i] = length[j];
length[i]++;
if (maxn < length[i]) maxn = length[i];
}
printf( "%d\n ", maxn);

return 0;
}
[解决办法]
#include <iostream>
using namespace std;
int longest(int *array,int size,int index)
{
int elemnum = size - index + 1;
int *record = new int[elemnum];
for(int i = 0;i <elemnum;++i)
{
record[i] = 0;
}
int max = 0;
record[index-1] = 0;
for(int i = index;i <size;++i)
{
for(int j = index -1;j <i;++j)
{
if(array[j]> array[i])
{
max = max> record[j]?max:record[j];
}
}
record[i] = max + 1;
max = 0;
}
max = 0;
for(int i = 0;i <elemnum;++i)
{
max = max> record[i]?max:record[i];
}
return max;
delete[] record;
}
int main( )
{
int index;
int array[] = {68,69,54,64,68,64,70,67,78,62,98,87};
cout < < "Please input the index number: " < < endl;
cin > > index;
cout < < "The elem number of LDS start form " < < index < < " is " < < longest(array,12,index) < < endl;
return 0;
}