问题 4618 --环形数列找最大

4618: 环形数列找最大★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 468  解决: 145
[提交][状态][命题人:]

题目描述

在一个长度为 n 的环形数列中,找出 k 个相邻数字之和的最大值,并给出该序列的起始位置。

如在 4 1 0 2 9 5 6 7 3 6 这个数列中,我们认为该数列尾部的 6 和头部的 4 是首尾相连的,是一个环形数列。现要求找出 5 个相邻的整数之和的最大值。

长度为 10 的环形数列可以组成 10 个 子数列,它们分别为:

起始位置 5 个相邻的整数数列 该子数列之和
1
4 1 0 2 9 16
2 1 0 2 9 5
17
3  0 2 9 5 6
22
4 2 9 5 6 7
29
5 9 5 6 7 3
30
6 5 6 7 3 6
27
7
6 7 3 6 4
26
8 7 3 6 4 1
21
9 3 6 4 1 0
14
10 6 4 1 0 2
13

因此 5 个相邻整数之和的最大值为 30,该子数列的起始位置为 5。

输入

第一行有两个整数,分别为 n 和 k。 ( 2 <= n <= 1000, 1 <= k <= n )

第二行有 n 个整数。( 每个数的绝对值<=2000000 )

( 所有数据已经过检验,保证解是唯一的。)

输出

一行两个整数,分别为 k 个相邻整数之和的最大值以及该子数列的起始位置,空格隔开。

样例输入
Copy
10 5
4 1 0 2 9 5 6 7 3 6
样例输出
Copy
30 5

提示

来源

SZS 

[提交][状态]