MaximumSumIncreasingSubsequence.py

#!/bin/python3
import sys
from copy import copy

fstd="test2"
sys.stdin = open('%s.txt' % fstd, 'r')
input = sys.stdin.readline

# DP based Python  
# implementation of Maximum Sum  
# Increasing Subsequence (MSIS) 
# problem 
  
# constructMaxSumIS() returns the tupple:
# ( max sum of increasing subsequence, found subsequence )
def constructMaxSumIS(arr): 
    N = len(arr)
    
    # L[i] stores the Maximum Sum Increasing Subsequence that ends with arr[i]
    L=[ [] for _ in range(N) ]
    # L[0] is equal to arr[0]
    L[0].append(arr[0])
    
    # msis[i] stores the Maximum Sum of Increasing Subsequence that
    # ends with arr[i]
    msis = [0]*N 
    # Initialize msis values 
    msis[0]=arr[0]
  
    # Compute maximum sum  
    # values in bottom up manner 
    for i in range(1, N): 
        for j in range(i): 
            if (arr[i] > arr[j]) and (msis[i] < msis[j]): 
                msis[i] = msis[j]
                L[i] = copy(L[j])
        L[i].append(arr[i])
        msis[i]+=arr[i]

    # Find max 
    maxIndex=max(range(N), key=lambda i:msis[i])
    return (msis[maxIndex],L[maxIndex])

if __name__ == "__main__":
    print("Input sequence:")
    A=[]
    while(True):
        line=input().strip()
        try:
            num=int(line)
        except ValueError:
            break
        A.append(num)
    print(A)
    res=constructMaxSumIS(A)
    print("Max sum is {}".format(res[0]))
    print("Found sequence is: {} ".format(res[1]))