TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3955
  • 题目
  • P3955最大子段和
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    给出一列n(n<=100000)个数并将这列数的首数和尾数视为首尾相邻的环状的结构,求这些数字长度不大于k(1<=k<=n)的最大子段和。

    输入格式

    第一行,两个整数N和K
    第二行,N个空格间隔的整数,表示给出的N个数字。数字的范围[-10000,10000]

    输出格式

    一行,三个整数,第一个整数表示最大字段和,第二和第三个整数表示所选子段的起点和终点编号。
    如果有多种方案,输出起点编号最小的一种,如果还有多种方案,输出长度最短的一种。

    样例输入 1

    6 3
    6 -1 2 -6 5 -5

    样例输出 1

    7 1 3

    样例输入 2

    6 4
    6 -1 2 -6 5 -5

    样例输出 2

    7 1 3

    样例输入 3

    6 3
    -1 2 -6 5 -5 6

    样例输出 3

    7 6 2

    样例输入 4

    6 6
    -1 -1 -1 -1 -1 -1

    样例输出 4

    -1 1 1


    来源  改编自UDH5143