Tổng liên tiếp lớn nhất của mảng con trong JavaScript

Chúng ta cần viết một hàm JavaScript nhận vào một mảng các số nguyên dương và âm. Vì mảng cũng chứa các phần tử âm, tổng các phần tử liên tiếp có thể âm hoặc dương.

Hàm của chúng ta nên chọn một mảng các phần tử liên tiếp từ mảng sao cho tổng là lớn nhất. Cuối cùng, hàm nên trả về mảng đó.

Ví dụ:

Nếu mảng đầu vào là:

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

Thì tổng lớn nhất có thể là 7 và mảng con đầu ra nên là:

const output = [4, -1, -2, 1, 5];

Ví dụ

Dưới đây là mã nguồn:

const arr = [-2, -3, 4, -1, -2, 1, 5, -3]; const maximumSubarray = (arr = []) => {    let max = -Infinity;    let currentSum = 0;    let maxStartIndex = 0;    let maxEndIndex = arr.length - 1;    let currentStartIndex = 0;    arr.forEach((currentNumber, currentIndex) => {       currentSum += currentNumber;       if (max < currentSum) {          max = currentSum;          maxStartIndex = currentStartIndex;          maxEndIndex = currentIndex;       }       if (currentSum < 0) {          currentSum = 0;          currentStartIndex = currentIndex + 1;       }    });    return arr.slice(maxStartIndex, maxEndIndex + 1); }; console.log(maximumSubarray(arr));

Kết quả

Đầu ra trên console:

[ 4, -1, -2, 1, 5 ]

Giải thích: Đây là thuật toán Kadane (O(n)) để tìm maximum subarray sum. Hàm trả về cả mảng con chứ không chỉ giá trị tổng.