5 kyu

Maximum Subarray Sum II

276 of 547raulbc777
Description
Loading description...
Fundamentals
Data Structures
Algorithms
Mathematics
Logic
Sorting
View
AllIssues5QuestionsSuggestions8Show Resolved
  • Please sign in or sign up to leave a comment.
  • artem-totality Avatar

    This Kata has some tricky not obvious conditions, which made it difficult and annoying for solving! My strong dislike to this Kata!

  • 1skovalchuk1 Avatar

    Which order the subsets are expected?

  • saudiGuy Avatar

    python new test framework is required. updated in this fork

  • chunchunmaru0000 Avatar

    expected [ [ [ 76, 97, -5, 29, -48, 31, 80, 57, +0 ], [ 76, 97, -5, 29, -48, 31, 80, 57 ] ], 317 ] to deeply equal [ [ [ 76, 97, -5, 29, -48, 31, 80, 57 ], [ 76, 97, -5, 29, -48, 31, 80, 57, +0 ] ], 317 ]

    genious

  • akar-0 Avatar

    Go translation

  • akar-0 Avatar

    Rust translation, should be approved before D translation to avoid merge conflict, since D updates the description for more languages.

  • akar-0 Avatar
  • NunoOliveira Avatar

    Issues still need to be fixed...

  • akar-0 Avatar

    The design of the output is bad. Returning a one dimensional array or multidimensional one for the first element, depending on what you find, isn't pertinent and makes it impossible to translate to many languages. Independently, a tuple would be a better choice for Python.

  • Blind4Basics Avatar

    Hi Raul,

    I've done it in JS:

    Either the description and the tests are incomplete (fixed tests), or there is a problem with the internal solution (edit: or the random generator):

    Expected: '[[[56, -56, 51, 36, -24, 70, 59, -33, -39, -36, 44, 75, 27, 48, 83, -25, -14, -62, -89, 72, 51, 87], [51, 36, -24, 70, 59, -33, -39, -36, 44, 75, 27, 48, 83, -25, -14, -62, -89, 72, 51, 87]], 381]', 
But got:  '[[51, 36, -24, 70, 59, -33, -39, -36, 44, 75, 27, 48, 83, -25, -14, -62, -89, 72, 51, 87], 381]'

Array =  [ -20,-12,27,-6,-33,56,-56,51,36,-24,70,59,-33,-39,-36,44,75,27,48,83,-25,-14,-62,-89,72,51,87,-73,55,-2,-86,12,4,  62 ]
                              ^----------------------------------------------------------------------^  = yours
                                    ^----------------------------------------------------------------^  = mine and second of yours

    Problems being:

    1. the ...56,-56,... for one part: should we keep it or not?
    2. can we have overlapping subarrays or not? (imo, we shouldn't...?)

    Note that going through the array right->left with the current requirements would lead to this overlapping thing, but not going left->right. So maybe it would be better to forbid contiguous opposite values in the inputs. If you keep them, you'll need to create specific tests for that (both with the pair before and/or after the smaller subarray)

    side note: you really should use one unique output type. => [[[...]], n] for single matches too.

  • lechevalier Avatar

    Another suggestion: why returning [sub_array, max_sum] when there is only one sub-array reaching the maximal sum, instead of [[sub_array], max_sum] - the default result in all the other cases? Isn't it better to harmonize the len(...) == 1 case also?

  • lechevalier Avatar

    As the kate is translated, you should remove the /train/python in your link to the previous kata as players may not have solved in Python.

    Better, consider using this link as it doesn't use any id:

    https://www.codewars.com/kata/maximum-subarray-sum
  • user5036852 Avatar

    Two spelling mistakes in the description! ISSUE!!!! ISSUE!!!!!!

    "Mathias Metzer" -> "Matthias Metzger"

    Please fix as fast as you can! :-) :-)

  • smile67 Avatar

    Hi Raul, i think there's an error in your random tests (here i used Javascript), look here:

    ✘   Expected: [[6,39,32,27,35,-17,-49,62,-7,42,74,15,-62,-12,83,41,76,74,30,-43,8,98,18,4,-89,9,-76,53,3,-50,78,72],574],
            instead got: [[[6,39,32,27,35,-17,-49,62,-7,42,74,15,-62,-12,83,41,76,74,30,-43,8,98,18,4],[6,39,32,27,35,-17,-49,62,-7,42,74,15,-62,-12,83,41,76,74,30,-43,8,98,18,4,-89,9,-76,53,3,-50,78,72]],574]

    As you can see, the second one in my solution is your (single) solution, my first one is another solution with same sum=574. The last part of your solution (-89,9,-76,53,3,-50,78,72) is 0, so there are two correct solutions. There are generally 1-4 errors of this form inside your random block (rest works for me).

    PS: After 4 tries my solution was accecpted, so you can have a look;-)...

  • JohanWiltink Avatar

    Also, agree with unnamed - the special case when there is exactly one solution is inelegant, unnecessary and makes for extra work both when producing and consuming the output. (Consuming isn't applicable to a kata, but would be so IRL.)

  • JohanWiltink Avatar

    Could do with random test with more than one solution.

    Could also do with tests with more than two solutions.

  • JohanWiltink Avatar

    The details might mention we're not interested in sums <= 0, and we have to return [] in that case.

  • Unnamed Avatar

    It looks like an abuse of dynamic typing. First there's an if to return the result, then there would be ifs wherever it's used.

  • timp Avatar

    Random Tests fail if array of max subsets is in a different order:

    Random Tests
length of the arrays = 20
array = [-2, -3, -4, 1, 8, -6, -7, 5, -6, 1, 7, -8, 10, 5, -3, -8, 3, -8, 8, -2]
[[[1, 7, -8, 10, 5], [10, 5]], 15] should equal [[[10, 5], [1, 7, -8, 10, 5]], 15]

    Can the description be updated to specify in which order the max subsets are expected?