如何递归地找到列表中差异最大的序列？

Question

鉴于此网格：

grid = [[10,23,16,25,12],
        [19,11,8,1,4],
        [3,6,9,7,20],
        [18,24,4,17,5],
        [7,3,4,6,1]]

其奇数行之和与偶数行之和相差最大的序列是第1行到第3行的序列。这是因为(10 + 23 + 16 + 25 + 12) - (19 + 11 + 8 + 1 + 4) + (3 + 6 + 9 + 7 + 20) = 88这是最大的差值所有序列都是这样。

序列应该有一个偶数行和一个奇数行，因此它必须至少有 2 行。最大行数取决于网格的大小。

问题是我需要它来处理 O(log n) 时间复杂度。我的想法是使用递归将网格划分为 2 并从那里解决它。然而，它并没有像我想要的那样工作。

这是我的全部代码：

import math

class Sequence:
    
    def __init__(self,grids):
        self.grids = grids
        self.calculate_max_difference()
        
    def calculate_max_difference(self):
        # Get the odd and even rows using list slicing
        odd_rows = self.grids[::2]
        even_rows = self.grids[1::2]

        odd_sum = 0
        even_sum = 0
        for odd_lst in odd_rows:
            odd_sum += sum(odd_lst)
        for even_lst in even_rows:
            even_sum += sum(even_lst)

        self.diff = odd_sum - even_sum

def consecutive_seq(start,end,max,grids):
    middle = math.ceil((start+end)/2)
    sequence = []
    for row in range(end-start):
        sequence.append(grids[start+row])
    seq_ins = Sequence(sequence)

    if (end-start) <= 3 and (end-start) > 1:
        return seq_ins.grids
    
    upper_seq = consecutive_seq(start,middle,seq_ins.diff,seq_ins.grids)
    lower_seq = consecutive_seq(middle+1,end,seq_ins.diff,seq_ins.grids)
    greater_seq = upper_seq

    if upper_seq.diff < lower_seq.diff:
        greater_seq = lower_seq
    
    if greater_seq.diff < max:
        return seq_ins.grids

# Sample Input
grid = [[10,23,16,25,12],
        [19,11,8,1,4],
        [3,6,9,7,20],
        [18,24,4,17,5],
        [7,3,4,6,1]]
n = len(grid)

max_seq = consecutive_seq(0,n-1,0,grid)
print(max_seq)

我该怎么办？

Answer 1

首先，您实际上并不需要二维数组。您可以对所有行求和，并且仅将总和存储在一维数组中。例如

grid = [[10,23,16,25,12],
        [19,11,8,1,4],
        [3,6,9,7,20],
        [18,24,4,17,5],
        [7,3,4,6,1]]

转为

sums = [sum(row) for row in grid]  # sums = [86, 43, 45, 68, 21]

一旦你有了总和，你必须简单地反转奇数索引的符号

[86, 43, 45, 68, 21] becomes => [86, -43, 45, -68, 21]

获得这种格式的数据后，您可以使用 Finding the largest sum in a contiguous subarray 的算法，其时间复杂度为 O(n)。您可能需要对其进行一些小调整以包含至少 2 个数字。

此外，如果您只关心差异，则必须再次运行算法，但这次将偶数索引乘以 -1。

我真的不认为你能在 O(log n) 时间内解决这个问题。

如何递归地找到列表中差异最大的序列？

How to recursively find the sequence in a list with the highest difference?

python

recursion

big-o

time-complexity