数学考试 题解

代码有些繁琐，写不出O(nlogn)的方法。
这道题的大意就是选择两段没有交叉的部分使得和最大。
我这里的a[]可以直接用前缀和next[]存储输入，没必要用a[]；
可以用qzh[i] = next[i]- next[i-k]记录下每个K段的和；
然后用max[i]记录qzh[]前i项的最大值.
最后遍历数组，取出当前与max和最大的那一项即可.

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int T = (int)in.nval;
        for(int t=0;t<T;t++)
        {
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int k = (int)in.nval;
        long a[] = new long[n];
        long next[] = new long[n];
        long qzh[] = new long[n];
        long max[] = new long[n];
        long sum=-1000000000;
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            a[i] = (int)in.nval;
        }
            next[0] = a[0];
        for(int i=1;i<n;i++)
        {
            next[i] = next[i-1]+a[i];
        }
            qzh[k-1] = next[k-1];
            max[k-1] = qzh[k-1];
        for(int i=k;i<n;i++)
        {
            qzh[i] = next[i]- next[i-k];
            max[i] = Math.max(qzh[i],max[i-1]);
        }
            sum = qzh[2*k-1]+max[k-1];
        for(int i=2*k;i<n;i++)
        {
            sum = Math.max(qzh[i]+max[i-k],sum);
        }
            out.println(sum);
        }
        out.flush();
    }
                  }