Core Algo

• Similar to sliding window
• Sub array problems:
  • The brute force algo goes for O(n^2)
  • there is a way to calculate the largest sum by only making one pass on the array, bringing the complexity down to linear time
  • e.g. "Find a non-empty subarray with the largest sum" brute force
    
  • O(n) solution
    

Problems:

• https://neetcode.io/problems/maximum-subarray
• https://leetcode.com/problems/maximum-sum-circular-subarray/description/
• https://leetcode.com/problems/maximum-ascending-subarray-sum
• ~~https://leetcode.com/problems/longest-turbulent-subarray/description/
  • Solve using Iterative solution - https://neetcode.io/solutions/longest-turbulent-subarray