const numbers = [1, -3, 2 - 5, 7, 6, -1, -4, 11, -23];

// O(n^3)
const findMaxSubAry = numbers => {
  let answer = Number.MIN_VALUE;
  /**
   * Calculate all the possible values and pick the max one
   * All possible values should be
   * length = 1, 2, ,3 ... n
   *  Pick differnet start point
   */

  // For different lenght
  for (let l = 0; l < numbers.length; l++) {
    // O(n)
    // For different start
    for (let s = 0; s < l; s++) {
      // O(n)
      if (s + l >= numbers.length) {
        break;
      }
      let sum = 0;
      for (let i = s; i < s + l; i++) {
        // O(n)
        sum += numbers[i];
      }

      answer = Math.max(answer, sum);
    }
  }

  return answer;
};

console.log(findMaxSubAry(numbers));  // 19

 /**
  * Maximum Contiguous subarray algorithm
  * 
  * Max(i) = Max(i-1) + v(i)
  * Max(i-1) < 0 ? v(i) : Max(i-1)
  * 
  * Combining
---------
maxInc(i) = maxInc(i - 1) > 0 ? maxInc(i - 1) + val(i) : val(i)
max(i) = maxInc(i) > max(i - 1) ? maxInc(i) : max(i - 1)
  */
function maxSumSubArray(arr) {
  /**
   *   inx  | val   |  max_inc    | max 
   *          0       0            0
   *    0     -2      0            0
   *    1     -3      0            0
   *    2     4       4            4     ---> start = 2
   *    3     -1      3            4
   *    4     -2      1            4
   *    5     1       2            4
   *    6     5       7            7     ---> end  = 6
   *    7     -3      4            7             
   */

  let val = 0, max_inc = 0, max = 0, start = 0, end = 0;

  for (let i = 1; i < arr.length; i++) {
    val = arr[i];
    max_inc = Math.max(max_inc + val, val);
    max = Math.max(max, max_inc);

    if (val === max_inc) {
      start = i;
    }

    if (max === max_inc) {
      end = i;
    }
  }

  if (end === 0) {
    end = start;
  }
  console.log(start, end);
  return arr.slice(start, end + 1);
}

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