You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in SPOJ-MAXI

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

asked 01 Nov '17, 00:07

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

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

(01 Nov '17, 12:27) dishant_185★

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.

link

answered 01 Nov '17, 13:04

droy0528's gravatar image

5★droy0528
956
accept rate: 16%

edited 01 Nov '17, 13:14

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

(01 Nov '17, 13:12) dishant_185★

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

(01 Nov '17, 13:16) droy05285★
1

Thank you :)
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?

(01 Nov '17, 16:54) dishant_185★

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.

(01 Nov '17, 17:07) droy05285★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,739
×1,138

question asked: 01 Nov '17, 00:07

question was seen: 366 times

last updated: 01 Nov '17, 17:07