FilesExpand file tree

 master

/

longest_sub_array.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

34 lines (27 loc) · 1.04 KB

 master

/

longest_sub_array.py

Copy path

Top

File metadata and controls

• Code
• Blame

34 lines (27 loc) · 1.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

Author : Yvonne

This is a pure Python implementation of Dynamic Programming solution to the

longest_sub_array problem.

The problem is :

Given an array, to find the longest and continuous sub array and get the max sum of the

sub array in the given array.

"""

class SubArray:

def __init__(self, arr):

# we need a list not a string, so do something to change the type

self.array = arr.split(",")

print(("the input array is:", self.array))

def solve_sub_array(self):

rear = [int(self.array[0])] * len(self.array)

sum_value = [int(self.array[0])] * len(self.array)

for i in range(1, len(self.array)):

sum_value[i] = max(

int(self.array[i]) + sum_value[i - 1], int(self.array[i])

)

rear[i] = max(sum_value[i], rear[i - 1])

return rear[len(self.array) - 1]

if __name__ == "__main__":

whole_array = input("please input some numbers:")

array = SubArray(whole_array)

re = array.solve_sub_array()

print(("the results is:", re))