ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1146. Maximum Sum

Show all messages Hide all messages

How do you get 0.03 s? Less than O(N^4) Alyosha Popovich 5 Mar 2002 12:43
Can you solve this problem in less time than O(N^4) ?
please email to scythe@toughguy.net
thank you
do you know... I have answers to all your questions :) 5 Mar 2002 22:44
an O(N) algorithm to solve this task : find the consecutive
subsequence with the largest sum of a given sequence of N integers ?
thank you xyz! your hint really inspires me Sam Green 6 Mar 2002 09:56
> an O(N) algorithm to solve this task : find the consecutive
> subsequence with the largest sum of a given sequence of N integers ?
Re: How do you get 0.03 s? Less than O(N^4) Copy_cat 11 May 2004 13:38
you precalculate sums in the matrix for O(n^3) and uses a DP
to reach O(n^2). I'll send my source later.

© 2000–2026 Timus Online Judge Team. All rights reserved.