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