#5 Maximum Subarray

#5 Maximum Subarray

Blind 75. Array

Imagine you have a lemonade stand and you keep track of your daily profits over a month. Some days you make money, and some days you might lose money because of expenses or bad weather. You want to find out the best period during the month where you made the most profit overall.

Day 1: $3

Day 2: -$2

Day 3: $5

Day 4: -$1

Day 5: $2

Day 6: $6

Day 7: -$3

Day 8: $1

Day 9: $4

Day 10: -$2

later we will see how we can find out the best period during the month to make profits.

Context about the problem:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

As usual before we solve the problem, let's first understand why it we need to understand this algorithm, what's the importance of asking this question or technique to solve this question?

Real world application of max sub array problem.

1. Facebook:
2. Trend Detection: Finding periods of high engagement or viral content spread.
3. Temperature Analysis:
4. Identifying periods with highest average temperature
5. Identify heat waves or significant temperature shifts over a specific period
6. Amazon:
7. Determine the period with highest sales to optimize inventory.
8. Analyse sales data and identify periods of peak demand to ensure inventory levels are optimized.
9. Google:
10. Use max subarray algorithm to analyze click through rate CTR data to determine the most effective periods for ad placements, optimising ad revenue.

direct and brute force approach:

multiple ways this can be solved using brute force 

but the point to be noted is how are you going to compare it in contiguous way?

we know we need to compare values so we need a loop and a nested loop,

the inner loop can be 

for( j = 0; j < nums.length; j++){

  if(j>=i){

    currentSum += nums[i]

    maxSum = Math.max(maxSum, currentSum)

  }

}

or it can be:

for(j = i; j< nums.length; j++){

  here also j only comparison continues to be contiguous

}

function bruteForce(nums) {

  let maxSum = nums[0]

  for(i = 0; i < nums.length; i++){

    let currentSum = 0

    for (let j = i; j < nums.length;j++){

      currentSum += nums[j]

      maxSum = Math.max(maxSum, currentSum) 

    }

  }

  return maxSum

} 

now let's see how we can optimize this

When we are dealing with

1. 1D array
2. Asking for max/min problem to solve
3. solve it in contagious way.

When we are dealing with this context, we can use kodana's algorithm .

function kodandeMaxSubArray(nums){

  let currentSum = nums[0]

  let maxSum = nums[0]

  for(let i = 1; i < nums.length; i++){

    currentSum = Math.max(nums[i], nums[i] + currentSum)

    maxSum = Math.max(maxSum, currentSum)

  }

}

kodandeMaxSubArray( [3, -2, 5, -1, 2, 6, -3, 1, 4, -2])

so the profit from our lemonade stand from the example is $9.

we can tweak this algorithm to record the starting and ending day as well to find the best days.

Here's the report from leetcode.