PYTHON CODE

PLEASE FOLLOW THE QUESTION'S REQUIREMENTS !!!!!!!

NO PRINT FUNCTION CAN BE USED, ONLY CAN USE RETURN

Task 2: Maximum sum increasing sub-sequence

You may not import any other libraries or modules.

Given a non-empty list of integers, write a function max sum(lst) that return a list of length of 2. The first element in output list should be an integer value representing the greatest sum that can be generated from a strictly-increasing sub-sequence in the list. The second element should be a list of the numbers in that subsequence. A sub-sequence is defined as a set of numbers that are not necessarily adjacent but in the same order as they appear in the list. Assume that there will be only one increasing sub-sequence with the greatest sum.

Input: a non-empty list of integers

Output: returns a list of length of 2. The first element in output list should be an integer value representing the greatest sum that can be generated from a strictly-increasing sub-sequence in the list. The second element should a list of the numbers in that sub-sequence.

Examples

a) Given lst1=[-1], calling max sum(lst1), will return [-1,[-1]].

b) Given lst2=[10,70,20,30,50,11,30], calling max sum(lst2), will return [110, [10, 20, 30, 50]].

c) Given lst3=[-5,-4,-3,-2,-1], calling max sum(lst3), will return [-1, [-1]].

d) Given lst4=[10,15,4,5,11,14,31,25,31,23,25,31,50] , calling max sum(lst4), will return [164, [10, 11, 14, 23, 25, 31, 50]].

Marks are given for the correct behaviour of the different functions: (a) 2 marks to find all the feasible solutions. 2 marks to find the optimal solutions.

THE RETURN OUTPUT MUST BE THE SAME AS THE EXAMPLE, RETURN [164, [10, 11, 14, 23, 25, 31, 50]], BE IN AN ARRAY CONSISTS OF 2 LENGTHS, NO PRINT

Need to use either brute force approach or backtracking to do the question.