求解数组中连续一段子数组和的最大值。

MaxSum.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 问题：
//     求解数组中连续一段子数组和的最大值。
// 
// 解答：特殊情况，全是负数的时候需要处理
//      先判定是否上次计算的和是否大于0
//      如果大于0则继续累计求和,否则就重
//      新取值,然后再跟已经记录过的最大和
//      进行比较, 直到遍历完整个数组.
// 注意: 
//      必须应该先,判断上次的求和结果是否
//      大于0，如果直接相加两个负数相加会
//      更小,所以不能处理全部负数的情况.
// 

int max_sum(int* a, int n)
{
  int maxSum = a[0]; // 此处为了方便处理全是负数的情况,如果忽略可以直接sum = 0
  int sum = 0, i = 0; // sum临时变量,用于存储计算和结果,以方便找到最大和.
  for (; i < n; i++) {
    sum = (sum > 0) ? (sum + a[i]) : a[i];  // 如果和小于0,则重新开始取值.如果两个负数相加会更小,所以必须要这个判断
    if (sum > maxSum)
      maxSum = sum;
  }
  return maxSum;
}

int max_sum2(int *a, int n)
{
  int maxSum = 0;
  int sum = 0, i = 0;
  for (i = 0; i < n; i++) {
    sum += a[i];
    if (sum < 0)
      sum = 0;
    else if (sum > maxSum)
      maxSum = sum;
  }
  return maxSum;
}

int shuffle(int *a, int n)
{
  int i = 0;
  if (rand() % 2) {
    for (; i < n; i++) {
      a[i] = rand() % 20;
      if ((rand() % 2) == 0)
        a[i] = -a[i];
      if (a[i] == 0)
        a[i] = rand() % 30;
    }
    return 0;
  } else {
    for (i = 0; i < n; i++)
      a[i] = -(rand() % 20);
    return 1;
  }
}

void print_array(int *a, int n)
{
  for (int i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}

int main(int argc, char **argv)
{
  srand(time(NULL));
  int a[10];
  int len = sizeof(a) / sizeof(a[0]);
  
  int which = shuffle(a, len);
  print_array(a, len);
  if (which)
    printf("sum %d\n", max_sum(a, len));
  else {
    printf("sum %d\n", max_sum(a, len));
    printf("sum2 %d\n", max_sum2(a, len));
  }
  return 0;
}