HDOJ 1003 Maximum Subarray Sum Problem

題目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

问题描述：给定一个数组a[0], a[1], ..., a[n-1]（其中n为数组长度），要求找出一个连续的子序列（即一段连续的元素），使其相应的和达到最大值。

一、暴力求解方法O(n^3)

直接的方法是枚举所有可能的连续子序列，并从中找出总值最高的那个。由起始索引i与结束索引j确定每个连续子序列的位置范围（其中0\leq i 且i\leq j ）。通过这种方式即可完成搜索过程。在计算过程中涉及三层循环结构：外层循环确定起始位置i（从0到n-1），中层循环确定结束位置j（从i到n-1），内层循环计算从a[i]到a[j]的所有元素之和。最终的时间复杂度为\mathcal{O}(n^3)，如代码所示：

 #include <iostream>

    
 using namespace std;
    
  
    
 int main()
    
 {
    
 	int T;
    
 	cin >> T;
    
 	while(T--)
    
 	{
    
 		int n, i, j, k;
    
 		cin >> n;
    
 		int *a = new