### Jass_Manak's blog

By Jass_Manak, history, 2 years ago,

I came across this problem on hacker earth contest. I was only able to think of a solution in O(n^2) time complexity. Can anyone share their approach with better time complexity.

• +6

 » 2 years ago, # | ← Rev. 2 →   0 Hello ! Consider OPERATION1, we have to find the maximum sub-array sum possible including an element i. This is easy if you know Kadane's Algorithm. For each index you have to store the largest sub-array sum you can achieve. Then, find out the maximum prefix achievable from index 0 till index i-1. Your answer is going to be that (maximum prefix sum till i-1) + (maximum sub-array sum achievable including element at index i(subarray should start from index i)).Similarly, in case OPERATION2, your answer will be (maximum suffix sum till i+1) + (maximum sub-array sum achievable including element at index i(this time the subarray should end at index i))NONE operation is just the Kadane's AlgorithmPython 3 Code : Maximum Subarray
 » 2 years ago, # |   0 Can you please give the link of problem..
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Actually it was from an earlier hiring challenge on hackerearth. I can't find this question in practice section now.
 » 2 years ago, # | ← Rev. 2 →   0 Why am I getting so many downvotes on this post?