- 论坛徽章:
- 0
|
本帖最后由 petery87 于 2010-09-16 11:07 编辑
回复 37# shangat
初始化条件改一下,max初始化为数组第一个元素,len初始化为1.
这样以下4种情况都可以处理了。
0. a[] = { -8, -3, -4, -7, -9, -6, -8, -5, -7}
1. a[] = { -3, -2, 7, -9, -1}
2. a[] = { 0, -2, -6, -6, -9, -4, -2, -1, -3}
3. a[] = { 0, -2, -6, -6, -9, 0, -2, -1, -3}
- #include <stdio.h>
- int main()
- {
- int a[] = { -8, -3, -4, -7, -9, -6, -8, -5, -7};
- //int a[] = {0, -1, -2, -3, 0, -4, -8};
- //int a[] = {1, 1, -3, -3, -4, 3, 4, -8, 2, 3};
- //int a[] = {9, -12, 120, 8, -20, 100, 30, -89, 20};
- int start; /* 子数组开始下标 */
- int temp_start; /* 临时计数的数组开始下标 */
- int len; /* 子数组长度 */
- int sum; /* 临时计数 */
- int max; /* 子数组的和 */
- int i;
- start = sum = temp_start = 0;
- len = 1;
- max = a[0];
- for(i = 0; i < sizeof(a)/sizeof(a[0]); i ++)
- {
- sum += a[i];
- if(sum < 0)
- {
- if(sum > max) /* 此时的sum即为 a[i],负值的情况只是简单的替换 */
- {
- max = sum;
- start = i;
- }
- temp_start = i + 1; /* 从下一个数组元素开始重新计算 */
- sum = 0; /* 舍弃前面的元素 */
- }
- else if(sum > max) /* 此时sum不小于0,前面的元素都已舍弃 */
- {
- start = temp_start; /* 找到新的和最大子数组,进行替换 */
- max = sum; /* 替换最大值 */
- len = i - start + 1; /* 计算子数组长度 */
- }
- }
- printf("start = %d, len = %d, max = %d\n", start, len, max);
- return 0;
- }
复制代码 |
|