在一个长度为 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。