Algo's

Question 1

Kaden’s algorithm to determine maximum subarray sum of an array

Answer 1

1. Set currentSum and MaxSum both equal to A[0]
2. loop thru each num from index 1 to end

• if currentSum was negative (before processing this next element) set currentSum = num to reset our starting point for the candidate subarray. This is because including a subarray with a negative sum as the prefix of a larger subarray is only going to decrease the larger subarray’s sum
• else add num to currentSum to continue expanding our candidate subarray
• update maxSum = max (maxSum, currentSum)

Question 2

Why does the currentSum = max(currentSum + num, num) trick work to remove the if statement in kaden’s algo?

Answer 2

if currentSum < 0, you’re going to be setting currentSum equal to num anyway, and num is > currentSum + num anyway, bc currentSum is negative. So that max statement works in this case.

if currentSum >= 0 && num >=0, you want to add num to the currentSum to keep expanding the candidate subarray. That max statement works in this case.

if currentSum >=0 && num <<0 s.t. the new current sum would be < 0 (aka |num| > currentSum), our max statement is going to set our currentSum equal to currentSum + num, which will be less than 0. Meaning next iteration the starting point of our subarray candidates will get reset again. Thus, that max statement works in this case.

if currentSum >=0 and num <0 & |num| < currentSum, currentSum would be properly updated to currentSum + sum, and won’t be erased on the next iteration

if currentSum >=0 and num >=0, same thing. CurrentSum would properly be updated to currentSum + sum, and won’t be erased on next iteration.

This max statement works as desired in all cases.

Question 3

What type of problems is kadens algorithm applicable?

Answer 3

..