Hints and ideas needed?


  • 0
    A

    Can someone provide some hints or ideas? I am stuck...


  • 1
    F

    In case you don't just want to look up how other people solved it (which is a great approach!):

    • The problem is labeled "easy", so it's not necessary to use more advanced approaches like dynamic programming. That implies there's a simple -- usually O(n) -- algorithm to solve the problem.
    • Try a naive approach to the problem: maybe you could keep track of each running total? This is rarely the right answer, since the amount of space you'll use with larger arrays is too large -- but it might give you ideas on how else to solve the problem.
    • Try an incremental logic approach (math/logic reasoning): Suppose you have an array that is its own largest subset already. Now pretend this is just the final answer that's embedded in a larger array - so to get backward to the original array, you need to append some numbers to the answer subset -- but they have to be the kind that would make the now-longer subset no larger than you already have. For example, suppose the answer subset is [4,-1,2,1]. Let's append some numbers: you can't add anything 1 or larger -- otherwise the answer would be larger than 6, so... [you can probably figure this out!]
    • Also try to add some extreme numbers in a sample array: if it's [...,2,3,-1000000,4,5,...] -- are there any cases when you can include the -1000000 in the answer subset?
    • Do you think there's a way to use running sums to use these new facts? When you have N of those, you don't really use any math logic, so maybe you can use only a few running sums, instead?

    HTH


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.