Jass_Manak's blog

By Jass_Manak, history, 2 years ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 Algorithm

Python 3 Code : Maximum Subarray

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please give the link of problem..

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

Why am I getting so many downvotes on this post?