微软，Google面试题 (3) —— 求最大子数组和

#include <stdio.h>

#include <stdlib.h>

//求最大子数组和

int getSum_v1(int *a, int length) { //穷举所有的子数组，找出和最大的

int greaterSum = 0;

int max = 0;

for (int len=1; len<=length; ++len) {

for (int idx=0; idx<len; ++idx) {

if (idx+len > length)

break;

for (int num=1; num<=len; ++num)

greaterSum += a[idx+num-1];

if (greaterSum > max)

max = greaterSum;

greaterSum = 0;

}

}

if (max == 0) { //全为非正数 max = a[0];

for (int i=0; i<length; ++i)

if (a[i] > max)

max = a[i];

}

return max;

}

int getSum_v2(int* a, int length) {

int greaterSum = 0, max = 0;

for (int idx=0; idx<length; ++idx) {

greaterSum += a[idx];

if (greaterSum < 0)

greaterSum = 0;

if (greaterSum > max)

max = greaterSum;

}

if (max == 0) { //全为非正数 max = a[0];

for (int i=0; i<length; ++i)

if (a[i] > max)

max = a[i];

}

return max;

}

int main() {

int a[] = {1,-2,3,10,-4,7,2,-5};

int ret = getSum_v1(a, sizeof(a)/sizeof(int));

printf("%d/n", ret);

return 0;

}

第二种思路比较巧妙，只需遍历数组一次。每当访问一个数，这个数和之前的累加和相加，构成新的累加和。如果这个新的和是正数，那么这个数对求最大和是有帮助的，负数是没有帮助的。所以，如果新的和是负数，我们把累加和清零。如果全部是非正数，那么需特殊处理，找出所有数中最大的那一个，返回即可。