algo: Kadane algorithm to resolve subarray max sum

[blade-sensei]

Depends on the specific conditions be have 2 GLOBAL ways to resolve tihs.

• If the problem ask to handle NON empty array
  • we should ask what to return if subarray is empty. 0 ? -Infinty
• If the problem doesnt ask to handle empty array, There is many ways of approch the problem.

  First approch

Consideres that for each iteration we compute the MAX_SUM unti index [i].

[ 2,  3]  --> index 1 (3) 
|--|
|------| = 
|--| + |3| (i)

First To do that we need to SUM of the contiguous subarray[i], We should not forget that [i] is also a subarray (of only 1 element). So we compute the the maximal the current_sum and the current element [i] (line 1 below). Now we know which if the subarray_sum is max (current_sum or [i]. But we still don't compare with [previous_sum] (subarray[i -1]) that can be greater than the current_sum. So compute this globalMax = Math.max(globalMax, currentMax); if this is first element or array of single element. the previousGlobalmax will be -infinity, to return the single element but in case it's negative it will works. Now this result is returned, globalMax will also be used for the next subarray[+1, +2..]

Important ❌

In summary ech iteration will have 3 the options of MAX_SUM at this [index]

• keep subarray[i+1] (current) ?
• keep [i] ? currentMax = Math.max(currentMax + number, nuber);
• keep the subarray[i-1] ? globalMax = Math.max(globalMax, currentMax);

//The expression: 
SUM_CURRENT = max_current_subarray[i-1] + [i]
max_current_subarray[i] = Max(SUM_CURRENT, [i])

//final code first approch

var maxSubArray = function(nums) {
  let currentMax = 0;
  let globalMax = -Infinity

  for (let number of nums) {
    currentMax = Math.max(currentMax + number, number);
    globalMax = Math.max(globalMax, currentMax);
  }
  return globalMax
};

Second approch

We considere that if we get negatives as sum if a subarray. the next contigious subarrays are not neccessary anymore to be calculated. Cause this negative subarray will decrease the max_sum. So we dont need to keep this subarray. Another sum subarray will be greater, so to start another sum we reset the sum_max to 0, this way, next iteration will set sum_max = sum_max + i, it means that we start another sum from i.

var maxSubArray = function(nums) {
  let currentMax = 0;
  let globalMax = -Infinity

  for (let number of nums) {
    currentMax = currentMax + number;
    globalMax = Math.max(globalMax, currentMax);
    currentMax = Math.max(currentMax, 0);
  }
  return globalMax
};

[blade-sensei]

Summary

Kadane Algorithm is used to get the maximal sum of contiguous subarray.

Basically we need to compare EACH sum of subarrays.

What is a a contigious subarray respects these criterias

• is a part of array that compose the MAIN/Principal array
• must be composed by subarrays/elements that are next each other
• subarray can also contain a single element like [10].

. Example:

principal array --> [-2, 10, 2, -12]

> one of contiguous subarray is [2, -12]
 - is its part of the principal array
 - is it composed by [2] [-12] that are next each other

> [10, -12] is a non contiguous subarray: don't respect second criteria

Understand the idea

Core idea (see dynamic programming)

The main idea behind Kadane algorithm is to resolve smallest problem by one one. So the idea:

• to iterate the array from start (index 0) to the last index to resolve the main problem
• each iteration acts like it was the main problem, we store the result and other necessary state for the next index.
• the next iteration will access to the previous value to compute his own problem.

Implement the idea with Kadane/ Which states we save

• We need to store an accumulated sum for the current level of subarray (levels will we explained further in a example).
• And also the global_max_sum computed by compare sum levels.

Here for each iteration

• the current subarray (index) uses the previous subarray (just behind -> it's important to create contiguous) to create a new subarray.
• this current subarray will used to check which of the
  • recently subarray[current]
  • and the subarray sum of previous level (or in other words the previous global_track_sum stored) is greater (MAX), the result is save in a global_track_sum.

as a subarray can also be composed by one element like [10] an index = subarray[index]

/**
 * if [-2, 10, 2, -12] 
 *      >
* In a classic brute force we change device the contiguous subarray this way:
* 1 -> [-2] [-2,10] [-2,10, 2] [-2,10,2,-12]
*2 -> [10]  [10,2]    [10,2,-12] 
*3 -> [2]   [2,-12]
*4 -> [-12]
* 
**/

 We can use the same structure for Kadane algorith we considered that we have 4 POTENTIALY max sum of each LEVEL. 

[blade-sensei]