-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmax_subarray.py
More file actions
77 lines (64 loc) · 2.29 KB
/
Copy pathmax_subarray.py
File metadata and controls
77 lines (64 loc) · 2.29 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import unittest
# TODO: note draw a good example to realize that max can also be negative
class MyTestCase(unittest.TestCase):
nums = []
memo = dict()
def test_something(self):
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = 6
self.assertEqual(self.find_max_subarray(nums), max_sum) # add assertion here
def test1(self):
self.assertEqual(self.find_max_subarray([1]), 1)
def test2(self):
self.assertEqual(self.find_max_subarray([5, 4, -1, 7, 8]), 23)
def test_minus1(self):
self.assertEqual(self.find_max_subarray([-1, -2, -3]), -1)
def find_max_subarray(self, nums):
# first deep search the sum and if > 0 keep otherwise ignore
self.nums = nums
self.memo = [0] * len(self.nums)
max = -10000
for i in range(len(self.nums)):
i_max = self.recursive_find_max(i, 0)
if i_max > max:
max = i_max
return max
def recursive_find_max(self, index, max):
#NOT NEEDED TO DO RECURSION
if index >= len(self.nums):
return 0
if self.memo[index] != 0:
return self.memo[index]
i_max = self.recursive_find_max(index + 1, max)
if i_max > 0:
self.memo[index] = i_max + self.nums[index]
else:
self.memo[index] = self.nums[index]
return self.memo[index]
def mine_second_solution(self, nums):
# Seems to be the best run time but a bit more complex
memo = [0] * len(nums)
memo[0] = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
# take this elem or sum of previous elems plus this
memo[i] = max(nums[i], memo[i-1] + nums[i])
if memo[i] > max_sum:
max_sum = memo[i]
return max_sum
def more_simple_solution2(self, nums):
# probably the best / most simple way
# no recursion
# just reset sum every time the sum is < 0
# otherwise continue summing elements one by one
cursum= 0
maxsum= -999999
for i in nums:
cursum+=i
if maxsum<cursum:
maxsum= cursum
if cursum<0:
cursum=0
return maxsum
if __name__ == '__main__':
unittest.main()