Tổng mảng con lớn nhất trong mảng vòng tròn dùng 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 arr làm đối số duy nhất. Chúng ta coi mảng này là mảng vòng tròn (circular), nghĩa là phần tử cuối theo sau bởi phần tử đầu. Hàm phải tìm và trả về tổng lớn nhất có thể của một mảng con không rỗng của arr.

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

Đầu vào

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

Đầu ra

const output = 4;

Giải thích

Vì mảng con mong muốn là [3, -1, 2].

Ví dụ

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

const arr = [2, -2, 3, -1];
const maxSubarraySumCircular = (arr = []) => {
  let max = arr[0];
  let min = arr[0];
  let currentMax = max;
  let currentMin = min;
  let sum = arr[0];
  for (let i = 1; i < arr.length; i++) {
    currentMax = arr[i] + Math.max(currentMax, 0);
    max = Math.max(max, currentMax);
    currentMin = arr[i] + Math.min(currentMin, 0);
    min = Math.min(min, currentMin);
    sum += arr[i];
  }
  return max < 0 ? max : Math.max(max, sum - min);
};
console.log(maxSubarraySumCircular(arr));

Kết quả

4