尺取

用尺取来节省时间，省去重复的操作。

对于下面的例题，通常的解法是双循环计算m长度的元素和，得出数值最大的结果。

#include<stdio.h>
long long int a[3000000];
int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
         int cnt=m,dd=n;
        long long int ans=0;
        for( int i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for(int i=0;i<m;i++)
            ans+=a[i];
        int  w=0;
        while(dd--)
        {
            int j=w;
            long long int f=0;
            while(cnt--)
            {
               f+=a[j];
               j++;
               j=j%n;
            }
            if(ans<f)
                ans=f;
            w++;
        }
       printf("%lld\n",ans);
    }
}

可以看到，w每次移动，sum都会重复加m-1个元素的值，重复操作；
而尺取算法可以完美规避。

第一步 设定左右端点，确定m长度元素的和为sum初始值，
右端点移动，为数组下标。cnt值更新，sum只加下一个值；
第二步 比较得较大数值ans
第三步 sum减去左端点值
第四步 更新左端点（后移）

如此，sum每次保留数值的同时只操作一次，避免重复计算。
最终代码实现如下：

#include<stdio.h>
long long int a[3000000];
int main()
{
   long long int n,m;
   while(~scanf("%lld %lld",&n,&m))
   {
       long long int sum=0,ans=0,left=0,right=0,cnt=0;
       for(long long int i=0;i<n;i++)
        scanf("%lld",&a[i]);
       while(left<n)
       {
         right=right%n;
         while(cnt-left<m)
         {
             sum+=a[right++];
             cnt++;
         }
         if(ans<sum)
            ans=sum;
         sum=sum-a[left];
         left++;
       }
       printf("%lld\n",ans);
   }
}

我们可以把sum形象的表示为一条毛毛虫，首先把它放在起点，建立首尾端，每次移动一格，身上数据只有部分是未知的，我们只要计算好未知部分即可^^

精确计算，不做重复计算