题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003
思路分析：该问题为最大连续子段和问题，使用动态规划求解；
1)最优子结构：假设数组为A[0, 1, 2,….., n]，在所有的可能的解中，即解空间中找出所有的解，可以知道，所有的解都为以A[j](j = 0, 1, …, n)
为尾的连续子段，则假设dp[j]表示以在数组A[1, 2, …, j]中以A[j]结尾的字段的最大的和，我们就可以刻画子空间中的所有解的特征；如果
dp[j] > 0,则dp[j + 1] = dp[j] + A[j + 1]，否则dp[j + 1] = A[j + 1]；对于该最优子结构的证明可以使用反证法来证明；
2)重叠子问题：明显，对于该问题的递归算法会反复求解相同的子问题，所有具有重叠子问题的性质；
代码如下：
#include <iostream>
using namespace std; const int MAX_N = + ;
int arr[MAX_N];
int pos_start, pos_end, num_arr; int Solve()
{
int l = , r = ;
int ans = INT_MIN, sum = ; for (int i = ; i <= num_arr; ++i)
{
if (sum >= )
{
r = i;
sum += arr[i];
}
else
{
l = r = i;
sum = arr[i];
} if (sum > ans)
{
pos_start = l;
pos_end = r;
ans = sum;
}
}
return ans;
} int main()
{
int case_num, case_id = ;
int ans = ; scanf("%d", &case_num);
while (case_num--)
{
scanf("%d", &num_arr);
for (int i = ; i <= num_arr; ++i)
scanf("%d", &arr[i]);
ans = Solve(); printf("Case %d:\n", ++case_id);
printf("%d %d %d\n", ans, pos_start, pos_end);
if (case_num > )
printf("\n");
} return ;
}