Kadane’s Algorithm

In this class, We discuss Kadane’s Algorithm.

For Complete YouTube Video: Click Here

The reader should have basic programming skills to solve Kadane’s Algorithm. Click here to learn basic coding.

Kadane’s Algorithm

Take an array of N integers. Find a continuous subarray that has a maximum sum?

Input: array of N elements.

Output: Maximum Sum

Example:

1) [1,3,5,-3,6]

Maximum sum = 12

2) [1,3,5,-3,1]

Maximum sum = 9

Time complexity = O(N)

Space complexity = O(1)

Click on the youtube link for intuition on the code.

Code:

def maxSubArraySum(arr,N):

    cmax=arr[0]

    gmax=arr[0]

    for i in range(1,N):

        if(cmax<0):

            cmax=arr[i]

        else:

            cmax+=arr[i]

        if(gmax<cmax):

            gmax=cmax

    return gmax

n = int(input(“eneter n value”))

arr = []

print(“eneter n elements”)

for i in range(n):

    x=int(input())

    arr.append(x)

val=maxSubArraySum(arr,n)

print(val)