微軟，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;

}

第二種思路比較巧妙，隻需周遊數組一次。每當通路一個數，這個數和之前的累加和相加，構成新的累加和。如果這個新的和是正數，那麼這個數對求最大和是有幫助的，負數是沒有幫助的。是以，如果新的和是負數，我們把累加和清零。如果全部是非正數，那麼需特殊處理，找出所有數中最大的那一個，傳回即可。