53. Maximum Subarray – Solution [Brute-Force to Best]
Here's the question link on LeetCode 53. Maximum Subarray: https://leetcode.com/problems/maximum-subarray/description Brute O(n^2)Optimal - O(n)Why can we not use prefix sums?Why does Kadane's work? Brute O(n^2) Try all possible subarrays using…