Dynamic Programming?

Dynamic Programming, short for DP, is the favorite of iSea. It is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems which are only slightly smaller and optimal substructure.
Ok, here is the problem. Given an array with N integers, find a continuous subsequence whose sum’s absolute value is the smallest. Very typical DP problem, right?

The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then a line with N integers Ai follows.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 1 000
3. -100 000 <= Ai <= 100 000

For each test case, output the case number first, then the smallest absolute value of sum.

2
2
1 -1
4
1 2 1 -2

Case 1: 0
Case 2: 1

iSea@WHU

首届华中区程序设计邀请赛暨第十届武汉大学程序设计大赛