Submit  All submissions  Best solutions  Back to list 
B_S_C_S  Biggest sum of a coherent subsequence 
Wersja polska  English version 
Your task is to find the biggest sum of a coherent subsequence.
Input
There is an unknown number (less than 10^{5}) of integers which are less than 10^{9}.
Output
One single number which is the biggest sum of a coherent subsequence.
Example
Input:
1000 100 5 8 4 100 1000
Output:
1801
Added by:  Piotr Kąkol 
Date:  20100412 
Time limit:  4.914s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: SCM qobi 
hide comments
20110613 21:21:17 Jander
@Piotr: Thanks  I'll have to have a good think on that. I wasn't completely satisfied that the 2nd half was optimal, but obviously it's linked into the first half too by your comment :) That is sneaky! But funky at the same time. Last edit: 20110614 15:07:34 

20110613 13:21:56 Piotr KÄ…kol
Both, but more the second half. ;) Good luck. :) 

20110610 14:44:00 Jander
Hmm. At the moment I can't see how to implement the same algorithm in a shorter manner. I think I might need to take a break and look at this again with fresh eyes :) Cheeky question  first half, or second half that would need to be changed? :) Last edit: 20110612 17:14:28 

20110610 13:54:56 Piotr KÄ…kol
@Jander  Implementation, sorry for the confusion. 

20110610 12:17:17 Jander
@Piotr  I figured my solution was somewhat different to clytorock's and yours due to the time taken to run. But I didn't think they were *that* different. I take it that we're using the same algorithm, just a different implementation ? 

20110610 11:11:09 Piotr KÄ…kol
challenger is my account. I made it of course to increase the rivalry. I look at users' codes and comparing few of them I try to remove some bytes (not change the algorithm). Comparing Your and clytorock's code I managed to change his program without changing the algorithm. So You would have to change half of Your program to reach 33 chars. But without challenger many users wouldn't even try to shorten their best results as they would think that it's impossible. I'm to show that they're wrong. ;) 

20110610 10:05:15 Jander
As usual challenger, I'm amazed at how you manage to remove that one extra byte :) How you do it, I have no idea. 

20100716 08:41:10 Piotr KÄ…kol
In: 123 23 345 324 32435 345 2343 324 3245 3245623 Out: 3272773 Your out: 3245623 

20100715 22:51:49 crappy coder
what's the catch here? i seem to be covering all the cases and still i get WA. 