• [A] Max Sum

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • You must learn the classic Dynamic Programming problems about “Max Sum of the
    Subsegment ”. Now you are given a cicle ring which contains n ( 1≤n≤100000 )integers
    a1, a2, ... , an with clockwise order. I want to know the “Max Sum of the Subsegment” in the ring.
  • 输入
  • Input starts with an integer T( T ≤50 ) denoting the test cases.
    For each test case, the first line will contain an integer n, then n signed 32 bits integers will
    be followed in the next line.
  • 输出
  • For each test case, print the case number and your answer.
  • 样例输入
  • 2
    4
    1 -1 -2 10
    5
    -3 4 1 -2 3
    4
    -1 -1 -1 -1
  • 样例输出
  • Case 1: 11
    Case 2: 6
    Case 3: -1
  • 提示
  • In the first sample, the max sum is 11, which equals 10 + 1(nth and 1th is adjacent)
  • 来源
  • Alex@NBUT
  • 操作

显示春菜