DSA Patterns (Multi-Lang)•Part 2: Arrays, Strings & Hash Maps (6 - 18)
Maximum Subarray (Kadane’s Algorithm).
In Simple Words:
Iterate through the array keeping track of currentSum. At each element, decide whether to add it to currentSum or start a new subarray fresh from nums[i].
- Time: $O(N)$ | Space: $O(1)$
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Alldef maxSubArray(nums: list[int]) -> int:
max_so_far = nums[0]
curr = nums[0]
for n in nums[1:]:
curr = max(n, curr + n)
max_so_far = max(max_so_far, curr)
return max_so_far