Tổng liền kề tối đa của mảng con trong JavaScript

Chúng tôi được yêu cầu 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 nên tổng các phần tử liền kề có thể là â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 nhau từ mảng có tổng giá trị lớn nhất. Cuối cùng, hàm sẽ trả về mảng đó.

Ví dụ -

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

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

Khi đó, tổng tối đa có thể là 7 và mảng con đầu ra phải là -

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

Ví dụ

Sau đây là mã -

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

Đầu ra

Sau đây là kết quả trên bảng điều khiển -

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