You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Longest Sequence that Makes the Greatest Sum

Nicholas Wong
Nicholas Wong

Question

输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18。

From a set of positive and negative integers, find the longest sequence that makes the greatest sum.
It is required to have the time complexity of O(n).

Solution

如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,
那么最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18

所有的东西都在以下俩行,即:

b:   0 1 -1 3 13 9 16 18 7 
sum: 0 1 1 3 13 13 16 18 18

其实算法很简单,当前面的几个数,加起来后,b<0后,
把b重新赋值,置为下一个元素,b=a[i]。
当b>sum,则更新sum=b;
若b<sum,则sum保持原值,不更新。

Code

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

int main() {
  int a[10] = {1, -8, 6, 3, -1, 5, 7, -2, 0, 1};
  printf("maxSum: %dn", maxSum(a, 10));
  return 0;
}
Algorithm

Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.