Maximum Sum Circular Subarray LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var maxSubarraySumCircular = function (nums) {
6
  let n = nums.length;
7

8
  // Kadane for single interval
9
  let curr = nums[0]; // dp[j] Maximum sum subbarray till j
10
  let ans = nums[0]; // Maximum of all dps till j i.e. max(dp[0], dp[1], ... dp[i], ...dp[j]);
11

12
  for (let i = 1; i < n; i++) {
13
    curr = nums[i] + Math.max(0, curr);
14
    ans = Math.max(ans, curr);
15
  }
16

17
  /**
18
   * If we don't find answer using kadane using above logic then that means only one thing
19
   * some answer is present in 1st half and second in other half (since it is circular array)
20
   **/
21

22
  let rightSum = new Array(n); // Sum from Right, used to represent 2nd half of the solution
23

24
  rightSum[n - 1] = nums[n - 1];
25

26
  for (let i = n - 2; i >= 0; i--) {
27
    rightSum[i] = rightSum[i + 1] + nums[i];
28
  }
29

30
  let maxRightSum = new Array(n); // Used to fast fetch max right sum till given point
31
  maxRightSum[n - 1] = rightSum[n - 1];
32

33
  for (let i = n - 2; i >= 0; i--) {
34
    maxRightSum[i] = Math.max(maxRightSum[i + 1], rightSum[i]);
35
  }
36

37
  /**
38
   * Now solution is max of:
39
   * [Sum of [A0 --- Ai] + Maximum [Ai+2 --- An]]
40
   * Considering i + 1 will be equivalent to kadane which we already discussed above.
41
   **/
42
  let leftSum = 0;
43
  for (let i = 0; i < n - 2; i++) {
44
    leftSum += nums[i];
45
    ans = Math.max(ans, leftSum + maxRightSum[i + 2]);
46
  }
47
  return ans;
48
};