Sử dụng thuật toán của Kadane để tìm tổng số tối đa của mảng con trong JavaScript

Vấn đề

Chúng tôi được yêu cầu viết một hàm JavaScript nhận một mảng các số nguyên (cả số dương và số âm), arr, làm đối số đầu tiên và duy nhất.

Hàm của chúng ta sẽ trả về tổng tối đa của bất kỳ mảng con nào trong thời gian tuyến tính

Local_maximum tại bất kỳ chỉ mục nào tùy ý i là giá trị lớn nhất của arr [i] và tổng của arr [i] andlocal_maximum tại chỉ mục i - 1.

Đây là những gì chúng ta sẽ áp dụng để tìm tổng mảng con tối đa trong một mảng theo thời gian tuyến tính.

Ví dụ:nếu đầu vào của hàm là -

Đầu vào

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

Đầu ra

const output = 6;

Giải thích đầu ra

Bởi vì mảng con có tổng tối đa là -

[4, -1, 2, 1]

Ví dụ

Sau đây là mã -

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));