import 'package:test/test.dart';
import 'dart:math';

int kadanesAlgorithm(List<int> array) {
  int maxEndingHere = array[0];
  int maxSoFar = array[0];

  for (int num in array.sublist(1, array.length)) {
    maxEndingHere = max(maxEndingHere + num, num);
    maxSoFar = max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

void main() {
  List<int> array;
  int maxContiniousSubarraySum;

  test(('.Check the response for each test case'), () {
    array = [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4];

    maxContiniousSubarraySum = kadanesAlgorithm(array);
    expect(maxContiniousSubarraySum, equals(19));
  });

  test(('.Check the response for each test case'), () {
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    maxContiniousSubarraySum = kadanesAlgorithm(array);
    expect(maxContiniousSubarraySum, equals(55));
  });

  test(('.Check the response for each test case'), () {
    array = [-1, -2, -3, -4, -5, -6, -7, -8, -9, -10];
    maxContiniousSubarraySum = kadanesAlgorithm(array);
    expect(maxContiniousSubarraySum, equals(-1));
  });

  test(('.Check the response for each test case'), () {
    array = [1, 2, 3, 4, 5, 6, -22, 7, 8, 9, 10];
    maxContiniousSubarraySum = kadanesAlgorithm(array);
    expect(maxContiniousSubarraySum, equals(34));
  });
}

问题陈述

给定一个整数数组 nums，找到其中一个连续子数组（包含至少一个数字），其具有最大的和，并返回该和。注意：子数组是数组的连续一部分。

第一个示例

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

第二个示例

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: [5,4,-1,7,8] has the largest sum = 23.

时间复杂度

O(N)

空间复杂度

O(1)

算法

其思想是跟踪以当前索引结尾的子数组的最大和。以当前索引结尾的子数组的最大和可以通过将当前元素添加到以先前索引结尾的子数组的最大和来计算。如果以先前索引结尾的子数组的最大和为负，则以当前索引结尾的子数组的最大和为当前元素。以当前索引结尾的子数组的最大和存储在变量 maxEndingHere 中。将以当前索引结尾的子数组的最大和与以先前索引结尾的子数组的最大和进行比较。如果以当前索引结尾的子数组的最大和大于以先前索引结尾的子数组的最大和，则将以当前索引结尾的子数组的最大和存储在变量 maxSoFar 中。以当前索引结尾的子数组的最大和作为输出返回。

演练

数组 = [-2,1,-3,4,-1,2,1,-5,4]

我们考虑数组的每个元素，并决定是否将其包含在当前子数组中或从其开始一个新的子数组。

两个变量的计算公式

current Sum = 0  Calculated by max(number, currentSum + number)
largest Sum = float("-inf")  Calculated by max(currentSum, largestSum)

遍历数组将如下所示

Consider -2
current_sum = max(-2, current_sum + -2) = max(-2, 0 + -2) = -2
largest_sum = max(-2, float("-inf")) = -2

Consider 1
current_sum = max(1, current_sum+1) = max(1, -2+1) = 1
largest_sum = max(1, -2) = 1

Consider -3
current_sum = max(-3, current_sum + -3) = max(-3, 1 + -3) = -2
largest_sum = max(-2, 1) = 1

Consider 4
current_sum = max(4, current_sum + 4) = max(4, -2 + 4) = 4
largest_sum = max(4, 1) = 4

Consider -1
current_sum = max(-1, current_sum + -1) = max(-1, 4 + -1) = 3
largest_sum = max(3, 4) = 4

Consider 2
current_sum = max(2, current_sum + 2) = max(2, 3 + 2) = 5
largest_sum = max(5, 4) = 5

Consider 1
current_sum = max(1, current_sum + 1) = max(1, 5 + 1) = 6
largest_sum = max(6, 5) = 6

Consider -5
current_sum = max(-5, current_sum + -5) = max(-5, 6 + -5) = 1
largest_sum = max(1, 6) = 6

Consider 4
current_sum = max(4, current_sum + 4) = max(4, 1 + 4) = 5
largest_sum = max(5, 6) = 6

因此，输出将为 6

视频讲解链接

• Kadane 算法求解最大子数组和问题