Sử dụng thuật toán Kadane tìm tổng lớn nhất mảng con trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số nguyên (cả dương và âm) arr làm đối số duy nhất. Hàm phải trả về tổng lớn nhất của bất kỳ mảng con nào trong thời gian tuyến tính.

Tổng cục bộ tại chỉ số i bất kỳ là lớn nhất của arr[i] và tổng của arr[i] và tổng cục bộ tại chỉ số i - 1. Đây là cách chúng ta áp dụng để tìm tổng mảng con lớn nhất trong thời gian tuyến tính.

Ví dụ, nếu đầu vào là:

Đầu vào

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

Đầu ra

const output = 6;

Giải thích

Vì mảng con có tổng lớn nhất là:

[4, -1, 2, 1]

Ví dụ

Dưới đây là mã thực hiện:

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
  let currentSum = 0;
  let maxSum = 0;
  for (let elem of arr) {
    const nextSum = currentSum + elem;
    maxSum = Math.max(maxSum, nextSum);
    currentSum = Math.max(nextSum, 0);
  }
  return maxSum;
};
console.log(maxSequence(arr));

Kết quả

6