CODEWITHSUNDEEP
python-3.xalgorithmsub-array
fiendfire28
fiendfire28

Reputation: 301

Maxumum non-contigious subarray in Python

I have to fing an increasing non-contigious subarray with maximum sum using Python. For example, if I have an array [5, 2, 4, 3, 7, 7], than I have to output [2, 4, 7]. Output given is increasing, have the maximum sum among all the possible increasing subarrays.

Upvotes: 1

Views: 85

Answers (1)

Carlo Zanocco
Carlo Zanocco

Reputation: 2019

Take a look at this code:

def elaborate(A):# Iterative function to princreasing subsequence with the maximum sum
    n = len(A)

    # values[i] stores the increasing subsequence having maximum sum
    # that ends with A[i]
    values = [[] for _ in range(n)]
    values[0].append(A[0])

    # sum[i] stores the maximum sum of the increasing subsequence
    # that ends with A[i]
    sum = [0] * n
    sum[0] = A[0]

    for i in range(1, n): # start from second element in the list
        for j in range(i):# do for each element in sublist[0..i-1]
            # find increasing subsequence with maximum sum that ends with
            # A[j] where A[j] is less than the current element A[i]
            if sum[i] < sum[j] and A[i] > A[j]:
                values[i] = values[j].copy()    # update increasing subsequence
                sum[i] = sum[j]     # update maximum sum

        values[i].append(A[i])  # include current element in increasing subsequence
        sum[i] += A[i]  # add current element to maximum sum

    j = 0    # j will contain index of values
    for i in range(1, n):
        if sum[i] > sum[j]:
            j = i

    # print values
    print(values[j])

A = [5, 2, 4, 3, 7, 7] 
elaborate(A)

# OUTPUT: [2, 4, 7]

The time complexity of above solution is O(n^2) and auxiliary space used by the program is O(n^2)

Upvotes: 1

Related Questions