Sub arrays

Question 1

Maximum sum in a subarray

Answer 1

1. Can use dp or currSum
2. dp[i] = currNo + dp[i - 1]
3. maxSum = max(maxSum, dp[i])

Question 2

Maximum Size Subarray Sum Equals k

Answer 2

1. HashMap
2. map.put(currSum, j)
3. currSum = k, maxLen = j + 1
4. map.contains(currSum - k) i = currSum - k
   maxLen = max(maxLen, j - i)

Question 3

Count of Subarray Sum Equals K

Answer 3

1. HashMap
2. map.contains(currSum - k)
   count += map.get(currSum - k)
3. map.put(currSum, map.getOrDefault(currSum, 0) + 1)

Question 4

Maximum Product Subarray

Answer 4

1. maintain min and max
2. find the max = max(currNo, max(currSum * max, currSum * min))
3. similarly for min
4. maxProduct = max(maxProduct, max)