It has been some time in my career since I had to really analyze an algorithm and come up with an efficient way to solve a problem. When I do, it can really tax my brain.
Perhaps you have the same issue. It would bring me comfort to know that I am not the only one with this problem.
Perhaps you were never presented with a particular type of problem. Perhaps you never learned how to create an algorithm and determine how efficient it is. Perhaps it has just been a really long time since you had a real world problem that required a really smart and efficient solution and "good enough" has been, well, good enough. Let's face it, there are plenty of us that do not work in a life-or-death environment or where the pressure to optimize everything is paramount.
After being stumped on how to compute the largest sub-array with a maximum sum I decided to do a little research on how this could be solved.
There are several ways you can implement this solution. We will consider a few of them.
- Brute-Force. Just look at every possible combination and choose the best one.
- Divide and Conquer. This approach will divide the problem into a smaller problem and solve the smaller problems.
- Kadane's algorithm