求子数组的最大和 题目： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值以及这个子数组。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2， 因此输出为该子数组的和18。
解法：
1 int find_max(int *array, int n) 2 { 3 int i; 4 int sum; 5 int start, end; 6 int tmp; 7 8 sum = 0; 9 tmp = 0; 10 start = end = 0; 11 12 for (i = 0; i < n; i++) 13 { 14 if (tmp < 0) 15 { 16 start = i; 17 tmp = array[i]; 18 } 19 else 20 { 21 tmp += array[i]; 22 } 23 if (sum < tmp) 24 { 25 sum = tmp; 26 end = i; 27 } 28 } 29 if (start <= end) 30 { 31 printf("sum = %d, start = %d, end = %d./n", sum, start, end); 32 33 for (i = start; i <= end; i++) 34 { 35 printf("%d,", array[i]); 36 } 37 printf("/n"); 38 } 39 else 40 { 41 printf("All negative numbers./n"); 42 } 43 return 0; 44 } 45 46 int main() 47 { 48 //int array[] = {-1, -1, -2, -1, -3, -1, -1}; 49 int array[] = {-1, 3, -2, 5, 3, -1, 1}; 50 int n = sizeof(array)/sizeof(int); 51 find_max(array, n); 52 return 0; 53 } 54
