5 kyu
Compute the Largest Sum of all Contiguous Subsequences
413 of 1,160LesRamer
Loading description...
Mathematics
Fundamentals
Algorithms
This comment has been reported as {{ abuseKindText }}.
Show
This comment has been hidden. You can view it now .
This comment can not be viewed.
- |
- Reply
- Edit
- View Solution
- Expand 1 Reply Expand {{ comments?.length }} replies
- Collapse
- Spoiler
- Remove
- Remove comment & replies
- Report
{{ fetchSolutionsError }}
-
-
Your rendered github-flavored markdown will appear here.
-
Label this discussion...
-
No Label
Keep the comment unlabeled if none of the below applies.
-
Issue
Use the issue label when reporting problems with the kata.
Be sure to explain the problem clearly and include the steps to reproduce. -
Suggestion
Use the suggestion label if you have feedback on how this kata can be improved.
-
Question
Use the question label if you have questions and/or need help solving the kata.
Don't forget to mention the language you're using, and mark as having spoiler if you include your solution.
-
No Label
- Cancel
Commenting is not allowed on this discussion
You cannot view this solution
There is no solution to show
Please sign in or sign up to leave a comment.
Not bad)
Scala translation
Java Translation
I just take my solution from wikipedia everytime i see a question like this
JS update fork
Replace those gross math.random calls with lodash and i'll approve
Done. Lmk if I missed any.
lgtm
isnt that a duplicate of maximum subarray sum ?
Well, you can pass the linked kata with an O(n^2) algorithm. In this one, you need O(n) to pass. So, this one is not really a duplicate.
oh sorry, i wasnt aware, the other is tagged "performance" as well
Other one should be remade and reranked at 7kyu, right now the requirements aren't even consistent across languages for it.
This comment has been hidden.
Kata is already tagged performance.
I am unconvinced that providing the test parameters and expected time complexity in the description would help in this instance. If someone doesn't arrive at a working approach on their own they won't know what to do with that information in the first place.
python new test framework is required. updated in this fork
Approved by someone
Cool kata)
Go translation
Rust translation
D translation
classic
My code fails at the random tests, gets messages like 'Expected: 18, instead got: 39998'. When print the maximum of the array, it's always 99, i.e. bigger than the expected number. Thus a single element array of 99 would be greater than the expected number. Something wrong here?
Can you copy and paste the actual messages you got? 18 is a lot more than 99 less than the "instead got" number you cite 39998.
Be sure to include the language you're attempting. If you can, add print statements so you can include the input as well.
This info will go a long way toward determining the issue.
Marking as resolved.
Python translation
Please approve.
Haskell translation
Please review and approve along with Ruby and Python below
Python Ruby
Please review and approve translations
you missed Python
Is this one working? I'm able to run the sample test cases (completed in 538ms), but the attempt request always fails with network error.
This one is working as intended.
Suggestions:
performancetagO(n)( possiblyO(n log n)) solution -O(n²)or worse is not going to cut itDo you mean "largest sum of all increasing subsequences" (in other words with consecutive positions)? Maybe I read too fast and didn't see that precision:-(
I've reviewed the mathematics term "subsequence" and your interpretation appears correct. While I don't want to be pedantic, 'increasing subsequence' seems to suggest 'in sorted order.' How about adding 'contiguous' - as in: "Largest sum of all contiguous subsequences"?
Edit: I've updated the wording in the title and details.
Thanks for the precision, contiguous seems perfect. Maybe "Largest Sum of all Contiguous Subsequences" would have been sufficient: at CW what do we do if it is not computing?:-)
After updating my wording, I noticed that there were at least two other existing duplicate kata.
Having discovered this after the fact, should I rewrite this kata to be generator/enumerable based? Leave it alone? Remove the kata? Something else?
In principle duplicate katas are not permitted... This problem of the largest sum is a classic. Maybe you could simply ask for a return being an array with the largest sum + index of the start and index of end of the subarray giving the largest sum. I think it would then be different enough for not being considered as a duplicate. This would not give you too much trouble (you already know the start and end indexes) except that you will have to rewrite a bit the tests:-(