Max Sum Increasing Subsequence

Write a function that takes in a non-empty array of integers and returns the greatest sum that can be generated from a strictly increasing subsequence in the array, as well as an array of the numbers in that sequence.

A subsequence of an array is a set of numbers that aren’t necessarily adjacent to each other in the array but that are in the same order as they appear in the array.

For instance, [1, 2, 4] form a subsequence of array [1, 5, 2, 0, 4].

Sample input:

array = [1, 7, 2, 3, 5, 1, 3]

Sample output:

[11, [1, 2, 3, 5]]

def maxSumIncreasingSubsequence(array):
    """
    We'll use DP to create an array of same length to store maxsum generated by all
    elements before a given index, including the value on the index. 
    Then, we'll keep track of potential sequences in another array. Here, we save the index
    of the previous element that contributed to the maxsum at the present index's position.
    
    O(n^2) time | O(n) space
    
    """
    sums = [num for num in array]
    sequences = [None for i in array]
    
    # store the index that contains the max sum
    maxSumIndex = 0
    for i in range(len(array)):
        for j in range(0, i):
            currentSum = sums[j] + array[i]
            if array[j] < array[i] and currentSum >= sums[i]:
                sums[i] = currentSum
                # store the position of the index that has influenced the current sum
                sequences[i] = j
        # update the maxSumIndex if a bigger sum exists in sums array
        maxSumIndex = i if sums[i] >= sums[maxSumIndex] else maxSumIndex
    
    return [sums[maxSumIndex], buildSequence(array, sequences, maxSumIndex)]
        

def buildSequence(array, sequences, currentIndex):
    """Backtrack while appending the values of the indices we saved"""
    sequence = []
    while currentIndex is not None:
        sequence.append(array[currentIndex])
        currentIndex = sequences[currentIndex]
    return list(reversed(sequence))

array = [1, 7, 2, 3, 5, 1, 3]
maxSumIncreasingSubsequence(array)

[11, [1, 2, 3, 5]]