昨天笔试看到一个求子数组最大和,参考这里,http://blog.csdn.net/v_JULY_v/…,写了一下,复杂度 O(n)
#include <stdio.h> int max_sum(int *a, int n) { int max = a[0]; int sum = 0; for (int i=0; i<n; i++) { if (sum < 0) { sum = a[i]; } else { sum += a[i]; } if (sum > max) { max = sum; } } return max; } int main() { int a[] = {1, -2, 3, 10, -4, 7, 2, -5}; printf("%dn", max_sum(a, sizeof(a)/sizeof(int))); }