Python 中最大的非连续子数组

Question

我必须使用 Python 计算一个具有最大总和的递增非连续子数组。例如，如果我有一个数组 [5, 2, 4, 3, 7, 7]，那么我必须输出 [2, 4, 7]。给定的输出是递增的，在所有可能递增的子数组中求和最大。

Answer 1

看看这段代码：

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]

上述解的时间复杂度为O(n^2)，程序使用的辅助space为O(n^2)

Python 中最大的非连续子数组

Maxumum non-contigious subarray in Python

algorithm

sub-array

python-3.x