Kadane’s Algorithm in Python

Kadane’s Algorithm

Kadane’s Algorithm is an amazing way to find the contiguous sub-array with maximum sum. This type of problem falls under Dynamic programming. So, we’re going to solve this problem using GeeksforGeeks requirement structure.

We have an array ‘arr’ of ‘N’ integers. 

Input: The first line of input contains an integer T denoting the number of test cases.

  • The first line contains a single integer N denoting the size of array.
  • The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.

Output: Print the maximum sum of the contiguous sub-array in a separate line for each test case.

                                                       GeeksForGeeks link: Link

SOLUTION BODY

def solution(nums):
    
        for i in range(1, len(nums)):
            if nums[i - 1] > 0: 
                nums[i] += nums[i - 1]
    
        return max(nums)

Execution Time: 0.4 seconds

INPUT BODY

def inputList(n):
    
    while True:
        print(f"Enter space separated elements of size {n}")
        array = [int(num) for num in input().split()]
        if len(array) == n:
            break
        else:
            print("Entered value doesn't match with size N provided")

    return array

MAIN BODY

def main():
    while True:
        try:
            T = int(input("Enter integer T denoting the number of test cases: "))
            array = {}
            
            for num in range(T):
                N = int(input("Enter integer N denoting size of array: "))
                array[num+1] = inputList(N)
                print("")            
                sums = solution(array[num+1])
                
                print(f"the maximum sum of the contiguous sub-array in {array[num+1]} is {sums}n")
            break
        except Exception as e:
            print(e)   
main()
Enter integer T denoting the number of test cases: 2
Enter integer N denoting size of array: 5
    Enter space separated elements of size 5 1 2 3 -2 5
    
    the maximum sum of the contiguous sub-array in [1, 3, 6, 4, 9] is 9
    
Enter integer N denoting size of array: 4
    Enter space separated elements of size 4 -1 -2 -3 -4
    
    the maximum sum of the contiguous sub-array in [-1, -2, -3, -4] is -1
Algorithm

Leave a Reply

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close