Maximum sum sub-array problem

The problem goes as : You're a programmer. You get placement in Mahindra. But you were dreaming of Google. Now all you can do is buy shares from Google. You have future predictions for the next 17 days as follows:


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Price 100 113 110 85 105 102 86 63 81 101 94 106 101 79 94 90 97

You decide when you buy, when you sell. Maximize the profit! Since you are a programmer, this isn't a big task for you right? So I wrote this brute-force code: Max profit of 43 when you buy on 7 day and sell on 11 day.

This works (and am proud of it!) but this is the reason why you didn't land a job at Google. Your code is slow! Here is a better approach:

This is divide and conquer, something that I've learnt very newly. It is fast, and works very well. But I don't understand why I am not getting the lower-limit and upper-limit (which was actually the goal) for the array 😥. Sorry about that 😣 Otherwise, this approach gives the correct sum value. There are more as such, like Kadane's algorithm, DP based algos, etc. This was just for an introduction to divide and conquer!
So, keeping it very brief, I move on next to

Upvote  5   Downvote
Created On: March 21, 2019 1:54 AM

There are no comments!

Create an account or login to write a comment

Supported by our Coding Partner