October 4th 2022

 

Some Interesting Algos, which can be very helpful at times and gives a short overview of solving many problems which can be quite sinuos at times.

The first algo, which is for finding the longest palindromic substring is known as Manacher's Algorithm.

'''October 4th 2022'''

def max_subMatrix(l:list[list[int]]):

    ''' A very interesting approach to the problem, uses the 

idea quite like the one used to find the 

        largest palindromic substr of maintaining a 2D array 

for getting the max size of a subMatrix with all 1's

    '''

    r=len(l)

    c=len(l[0])

    max_size=0

    

    #The sub matrix for maintaining the record of the 

#sizes of matrices

    s=[[0 for i in range(c)] for j in range(r)]

    

    #Initialize the elems of top row and first column 

#as it is from l

    for i in range(r):

        for j in range(c):

            if i==0 or j==0:

                s[i][j]=l[i][j]

    

    #We'll just check the remaining elems of the list 'l' 

#on the basis of the elems of the subMatrix 's'

    for i in range(1,r):

        for j in range(1,c):

            if l[i][j]==1:

                s[i][j]=min(s[i][j-1],s[i-1][j-1],s[i-1][j])+1

            else:

                s[i][j]=0

            if s[i][j]>max_size:

                max_size=s[i][j]

    

    #If needed then print the submatrix with all 1's, we 

#don't need to track the indices as the matrix will be

    #square and all 1's so we can print it directly

    for i in range(max_size):

        for j in range(max_size):

            print(1,end=" ")

        print()

    print("Printing through other method.")

    for i in range(max_size):

        print("1 "*max_size)

    

    #For clarity print the subMatrix obtained at the end of the prog

    for elem in s:

        print(elem)

    #Return the max possible size of the matrix

    return max_size

'''Space Optimized Solution for above Algo.'''

def max_subMatrix2(l):

    '''We'll just maintain the record of two rows(previous and current) 

unlike the last algo.'''

    r=len(l)

    c=len(l[0])

    max_size=0

    entrie=0

    s=[[0 for i in range(c)] for j in range(2)]

    for i in range(r):

        for j in range(c):

            if(l[i][j]):

                if(j):

                    entrie=min(s[0][j-1],s[1][j-1],s[1][j])+1

            else:

                entrie=0

            #Now update s subarray(Get new entries in s[1][j] and 

#store previous ones(s[1][j]), in s[0][j])

            s[0][j]=s[1][j]

            s[1][j]=entrie

            if entrie>max_size:

                max_size=entrie

    for i in range(max_size):

        print("1 "*max_size)

    return max_size

'''Algo for Largest Sum of a Contiguous Subarray'''

def largest_sum(l):

    current_max=0

    largest_max=0

    n=len(l)

    for i in range(n):

        current_max+=l[i]

        print("Current_max is:",current_max)

        if current_max>largest_max:

            largest_max=current_max

        if current_max<0:

            current_max=0

    return largest_max

def main():

#     sample_ls=[

#         [0,1,1,1,0],

#         [1,1,1,1,1],

#         [0,1,1,1,0],

#         [1,0,0,0,1],

#         [1,1,0,1,0]

#     ]

#     print(max_subMatrix2(sample_ls))

    sample_l=[1,-1,-2,3,4,5,-3,-5]

    print(largest_sum(sample_l))

if __name__=="__main__":

    main()