Problem

Given an array of integers, find the largest sum of a contiguous subarray.
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

Solution

// Solution:
// The solution is to iterate through the array and keep track of the current sum and the max sum.
// If the current sum is less than 0, then we reset the current sum to 0.
// If the current sum is greater than the max sum, then we update the max sum.
// This solution is optimal because we only iterate through the array once.

function maxSubArray(arr) {
  let currentSum = 0;
  let maxSum = 0;

  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];
    if (currentSum < 0) {
      currentSum = 0;
    }
    if (currentSum > maxSum) {
      maxSum = currentSum;
    }
  }

  return maxSum;
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));