[daily coding] Maximum continuous sum

problem

code

1st try: Brute force

var maxSum = numbers => {
  if (numbers.length == 0) return 0;
  
  let max = 0;
  for (let i = 1; i < numbers.length; i++) {
    // j + i <= numbers.length
  	for (let j = 0; j + i <= numbers.length; j++) {
      let sum = 0;
      for (let k = j; k < j + i; k++) {
      	sum += numbers[k];
        console.log(i, j, k, numbers[k], sum);
      }

      if (max < sum) max = sum;
    }
  }
  return max;
}
maxSum([34, -50, 42, 14, -5, 86])

Time: O(N^3)
Space: O(1)

2nd try: window sliding

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        
        int maxSoFar = Integer.MIN_VALUE;
        
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                maxSoFar = Math.max(sum, maxSoFar);
            }
        }
        
        return maxSoFar;
    }
}

time: O(N^2)
space: O(1)

3rd try: Kadane’s Algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0];
		
        max_so_far = -inf
        curr_sum = 0
        for n in nums:
            if (curr_sum + n > n):
                curr_sum += n
            else:
                curr_sum = n
            
            max_so_far = max(curr_sum, max_so_far)
            
        return max_so_far

time: O(N)
Space: O(1)

Kadane's algorithm 이란? (설명)