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

Given this grid:

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]]

The sequence with the greatest difference between the sum of its odd rows and the sum of its even rows is the sequence of row 1 to row 3. This is because (10 23 16 25 12) - (19 11 8 1 4) (3 6 9 7 20) = 88 which is the maximum difference out of all sequences like this.

The sequence should have an even row and an odd row so it must have at least 2 rows. The maximum number of rows depends on the size of the grid.

The problem is I need it to work on an O(log n) time complexity. My idea is to use recursion to divide the grid into 2 and solve it from there. However, it doesn't work as I wanted to.

This is my whole code:

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)

How should I go about this?

CodePudding user response：

Firstly you don't really need a 2d array for this. You can sum up all the rows and only store the sums in a 1D array. So for example

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]]

turns in to

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

Once you have the sums you have to simply invert the signs for odd indices

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

Once you have the data in this format, you can use the algorithm for Finding the largest sum in a contiguous subarray which has a time complexity of O(n). You might have to make a few small tweaks to that to include at least 2 numbers.

Also if you care only about the difference, you will have to run the algorithm again but this time multiply the even indices by -1.

I really don't think you can solve this in O(log n) time.