Code Wars: Maximum subarray sum

https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c/train/javascript

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.
Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

SOLUTION:
var maxSequence = function(arr){
  let maxSum = arr[0]; //current highest consecutive sum or single element
 
  if (arr.find(item => item > 0) === undefined || arr.length === 0) {
    return 0;
  }
 
  for (let i = 0; i < arr.length - 1; i++) {
    let tracker = 0; //keeps track of consecutive sums. Reset at every 'pointer' change (outside loop).
   
    //check if each element is greater than all other consecutive sums
    if (arr[i] > maxSum) {
      maxSum = arr[i];
    }
    //since for loop doesn't reach end of array
    else if (arr[i+1] > maxSum) {
      maxSum = arr[i+1];
    }
   
    for (let j = i + 1; j < arr.length; j++) {
     
      if ( arr[i] + arr[j] + tracker > maxSum ) {
        maxSum = arr[i] + arr[j] + tracker;
      }
      tracker += arr[j];
    }

  }
  return maxSum;
}

Comments

Popular posts from this blog

Code Wars: Data Reverse (6 kyu)

Code Wars: longest_palindrome (6 kyu)

Code Wars: Find the odd int