Blind 75 — Day 5 (Maximum Subarray)
Ever get frustrated when your code times out even though your test cases pass? Well, I definitely understand how that feels! In today’s video, I find myself figuring out a basic solution though with terrible time complexity as I must admit. It’s important to understand that there are multiple different approaches to a solution!
Today I was unable to resolve that, but it gave me insight into thinking about problem-solving patterns and how I might be able better improve my skills! From today on, I will also include my learning process of what I learned from the problem through review and the correct solution.
My inital though process was to run a for-loop twice to examine first the value of the integer in the initial loop, and to then run a second loop to examine all the values after that integer. This would allow us to only examine the values after the initial loop integer and add those values to a “current value” variable. I would then compare that value to a variable named greatestSum and would override it if the sum of a group of integers that I found was greater. The video explains this process in a more digestible manner so please watch to find out more!
The roadblock we ran into today was again time complexity. It does not seem that running a double for-loop is time efficient and there are better methods for us to identify groupings of array values. I’ve learned that running two loops definitely is not O(n) and is O(n²) which makes me realize to learn more about time complexity!
Please see the solution below to see how we might be able to do so!
Explanation of Solution: https://zyrastory.com/en/coding-en/leetcode-en/leetcode-53-maximum-subarray-solution-and-explanation-en/
