Help in SPOJ-MAXI

help
,
1

Hello guys,
I was solving the problem MAXI from SPOJ but couldn’t figure out a solution. Any insights would be much appreciated.
Thanks :slight_smile:

1 Like
2

@likecs as you have set this question any tips would be much appreciated!

3

By seeing your post i have gone through problem maxi…i have solved it in O(n^2).But some comments claimed that they solved this in O(n).I can not figure out how they did it in O(n) but i there is solution in O(n) and it takes 0.0 s,mine takes 0.13 s.But for O(n^2) its dynamic programming if u see it carefully.
Hope this helps.

1 Like
4

Thanks for the reply. It would be great if you can give a link to your code!

5

https://ideone.com/eyTMjd if something is not clear to you in my code u can ask and Welcome :slight_smile:

6

Thank you :slight_smile:
Well I too had a O(n^{2}) algorithm in back of my mind. I thought it may not pass the time limit of 0.2 secs as n<=10^{4}.
Can you explain how will it pass the time limit?

1 Like
7

Because its asymptotic complexity not exact complexity :).
Inner loops upper bound keeps up decrements by 1 each time you run the loop.
So it n only at first iteration there after it will keep decrements and reduce the time.