I have converted the given samples in python tests, then I added a few more cases to help me thinking about an algorithm.
def test_provided_1(self): self.assertEqual(8, solution('-10,2,3,-2,0,5,-15')) # 1 def test_provided_2(self): self.assertEqual(12, solution('2,3,-2,-1,10')) # 2 def test_plain(self): self.assertEqual(5, solution('2,3')) def test_a_negative_first(self): self.assertEqual(3, solution('-2,3')) def test_a_negative_second(self): self.assertEqual(2, solution('2,-3')) def test_both_negative(self): self.assertEqual(-2, solution('-2,-3')) def test_a_negative_in_between(self): self.assertEqual(2, solution('1,-1,2'))The idea is, I am going to loop on the sequence keeping track of the candidate solution. I initialize it with the first value in the list, then I pass to consider the next element.
It is possible that the sum of the proposed solution with the current value is higher, so that would get the new tentative solution. Otherwise I would keep the original one.
But, consider for instance (1). If I simply add up the two values I get -8, that is better of -10. However I should consider just 2 as a better solution. To do that, I refine the check stated above. If the proposed solution is negative, there is no use in adding it up to the current value, I can discard it and keeping the new value as new candidate solution.
There is another problem, as seen in (2). What I should do when I see a negative number in the series after some positive numbers? The first idea could be consider close a subsequence and go looking for a new one. However this way of thinking is not rewarding here, where the full sequence, leads to a higher sum than its left and right parts.
To overcome this issue I introduce a second variable, acting as a tentative solution that keeps track of all the elements, negative included, until it gets negative.
After this thoughts, I written down this Python function:
def solution(line): head, *values = [int(x) for x in line.split(',')] # 1 result = head # 2 maybe = head for value in values: maybe = value if maybe < 0 else maybe + value # 3 if maybe > result: # 4 result = maybe return result1. The input line is split on commas, its values are converted in integers and assigned to two variables, a single number, the head of the list that is managed differently, and a list of numbers, containing all the other elements.
2. I assign the first value to both solution. The currently chosen, result, and the tentative one, maybe.
3. For each following element, I check if it is worthy to keep the previous values, stored in maybe, and add the current value, or throw away all the old stuff and just keep the new value, trying to create a new subsequence.
4. Only if the tentative solution is actually better than the currently chosen one, I change it accordingly.
Well, it works. Python script and unit test are on GitHub.
No comments:
Post a Comment