题目如下： 最大的和 一天，笨笨带着一道题目找到了你，希望你能帮她解决这道题目： 给你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;}   总结：虽然测试了几组数据，还通得过，但不知正确与否。其次，对动态规划的理解不深刻，用了很长的时间才写出来。数学功底不够扎实。不足之处还望高手指点。

评论