max = max - (-4) = 9，count++ （count = 3）
max = max - 7 = 2，count++ （count = 4）
max = max - 2 = 0，count++ （count = 5）
至此count计算完毕，共5个数在这个子数组里。知道了子数组在原数组中的位置，又知道了她的长度～那么就能确定她到底是什么样的了，不是么？
我不说话，就看看代码～
//子组长度
int max_sub_array_length(int arr[], int count)
{
int max_value = 0;
int starter = 0;
int length = 0;
max_value = max_sub_array(arr, count);
starter = max_starter(arr, count) - 1;
while (max_value > 0)
{
max_value -= arr[starter++];
++length;
}
return length;
}
至于怎么把它打印出来就交给大家来完成了，动手试试！！！
最后把全部示例代码列出来：
/************************************************* * *作者：钟凌霄 *时间：2014.1.6 *题目：求子数组的最大和问题 * *************************************************/ #include#include //*******************子数组最大和************************** int max_sub_array(int arr[], int size) { int i = 0; //一个记录原数组的游标 int sum = 0; //sum来记录前k个数的和(k < n) int max = -(1 << 30); //max记录我们找到的最大和，开始我们设置为-2^31 //循环到size位置，我们可以寻找子数组的子数组，即假设 { 1，-2, 3, 10, -4, 7, 2 } //当我们设size = 4，那么其实测试的数组就是{ 1, -2, 3, 10 }。 while ( i < size ) { //这就是我们前面提到的，sum一直向后加arr[i]，当sum < 0时，我们抛弃sum，就是跳过前k个数，因为 //前k个数不是最优的子结构，我们就将sum置0，从新开始。 sum += arr[i++]; if ( sum < 0 ) { sum = 0; } //当sum加上一个正数的时候(sum新) > (sum原)，而max就是(sum原)。于是我们更新max。 //当sum加上一个负数的时候(sum新) < (sum原)，max不更新。这就是为什么最后一个数 //一定是大于0的了 else if ( sum > max ) { max = sum; } } return max; } //*******************子数组起始位置************************* int max_starter(int arr[], int count) { //发现这3个和之前没啥区别 int i = 0; int max = -(1 << 30); int sum = 0; //那这两个又是什么意思呢？ //starter_final：是最大子组起始位置;额... 那个starter呢？ //这个starter是记录临时的起始值，说的挺别扭的，要不看看例子？ 对于int arr[] = {-1,3,5,-12, 7, 10, 3, -1} //第一个starter是2，即arr[1] = 3那里，因为(arr[0] = -1) < 0,则sum < 0,直接就跳到arr[1]那里从新开始了，所 //以我们看看这个starter都有哪些？ a = 3, a = 7这两部分，是吧？自己动手算算。也就是说starter记录着所有可能的 //开始位置，而这个starter_final通过比较记录着存在和最大的子数组的起始位置。 int starter = 0; int starter_final = 0; while ( i < count ) { sum += arr[i++]; if ( sum < 0 ) { starter = i; sum = 0; } else if ( sum > max ) { max = sum; starter_final = starter; } } //我们返回的是位置，需要加1，即arr[4] = 7,的位置在数组的第5位。 return (starter_final + 1); } //*********************子数组长度************************ int max_sub_array_length(int arr[], int count) { int max_value = 0; int starter = 0; int length = 0; max_value = max_sub_array(arr, count); starter = max_starter(arr, count) - 1; while (max_value > 0) { max_value -= arr[starter++]; ++length; } return length; } //**********************全部测试用例*********************** int main() { int arr[] = {-1,3,5,-12, 7, 10, 3, -1}; int a = 0; int b = 0; int c = 0; a = max_sub_array(arr, 6); b = max_starter(arr, 8); c = max_sub_array_length(arr, 5); printf( "子数组最大和：%d\n", a ); printf( "子数组起始位置：%d\n", b ); printf( "子数组长度：%d\n", c ); return 0; }
这里我们并没有将该代码完善化，如果要问的话，那当然是留给大家的作业了～
当我们取a = 1的时候是以个负数，那么该程序就会告诉你最大和是 -1073741824（哪来的？怎么解决）。还有一些问题就让大家去思考发现，并独立去解决了～恩，加油！
至此我们已经基本上把这道题弄明白了，如果有什么问题的话欢迎指正和留言。