题目如下：
最大的和
一天，笨笨带着一道题目找到了你，希望你能帮她解决这道题目：
给你n个数a[1], a[2], ..., a[n]，(0<n<=16,000, -1,000<=a[i]<=1,000)和0<L1<=L2<=n 求长度在[L1,L2]的连续若干个数a[i], a[i+1], ..., a[j], (即L1<=j+1-i<=L2) 使得a[i]+a[i+1]+...+a[j]取到最大值, 你只需要输出那个最大值即可。
由于n非常大，所以笨笨就算数学再好也无法很好的解决这道题目。这下该看你的了，身为计算机小组的你，应该能轻松搞定这道题目吧。
输入文件：
输入文件第一行为三个整数n，L1， L2， 接下来是用空格或者换行符隔开的n个数, 第i个数表示a[i]。
输出文件：
仅一个数，表示a[i]+a[i+1]+...+a[j]的最大值。
Sample Input
5 3 4
3 -1 -2 5 3
Sample Output
6
分析：这是一道求最值问题的试题。首先很自然就想到用动态规划思想。于是小弟就试着用这种思想去试试。程序如下：
#include <iostream>
using namespace std;
int N,l1,l2;
int a[16000];
int num[16000]; //当前取最大值时所包含的连续的元素个数
int maxValue[16000]; //第i个元素的最大值
int f(int n)//第n个元素的最大值，即为状态
{
if (n == 1)
{
num[n] = 1;
return maxValue[n] = a[1];
}
int max1 = a[n] + f(n-1); //当前的最大值
if (max1 <= a[n]) //如果比当前值要小，说明最大值为当前值
{
num[n] = 1;
max1 = a[n];
}
else num[n] = ++num[n-1];
//如果连续元素个数比l2要大，则去除多余的元素个数
if (num[n] > l2)
{
num[n] = l2;
max1 -= a[n-l2];
}
//如果连续元素个数比l1要小，则补足缺少的元素个数
if (n >= l1 && num[n] < l1)
{
for (int i = n-num[n]; i > n-l1+1; i--)
max1 += a[i];
num[n] = l1;
}
return maxValue[n] = max1;
}
int main()
{
cin >> N >> l1 >> l2;
for (int i = 1; i <= N; i++)
cin >> a[i];
f(N);
int maxD = maxValue[l1];
for (int i = l1; i <= N; i++)
if (maxD < maxValue[i])maxD = maxValue[i];
cout << maxD << endl;
system("pause");
return 0;
}
总结：虽然测试了几组数据，还通得过，但不知正确与否。其次，对动态规划的理解不深刻，用了很长的时间才写出来。数学功底不够扎实。不足之处还望高手指点。
评论