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?