forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum_increasing_subsequence.py
More file actions
38 lines (27 loc) · 956 Bytes
/
maximum_increasing_subsequence.py
File metadata and controls
38 lines (27 loc) · 956 Bytes
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
"""
Problem Statement
=================
Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array
such that the integers in the subsequence are in increasing order.
Complexity
----------
* Time Complexity: O(n^2)
* Space Complexity: O(n)
Video
-----
* https://youtu.be/99ssGWhLPUE
Reference
---------
* http://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/
"""
def maximum_sum_subsequence(sequence):
sequence_length = len(sequence)
T = [sequence[i] for i in range(sequence_length)]
for index_i in range(1, sequence_length):
for index_j in range(0, index_i):
if sequence[index_j] < sequence[index_i]:
T[index_i] = max(T[index_i], T[index_j] + sequence[index_i])
return max(T)
if __name__ == '__main__':
sequence = [1, 101, 10, 2, 3, 100, 4]
assert 111 == maximum_sum_subsequence(sequence)