Golang Program to Implement Kaden\'s Algorithm

There is a famous maximum sum subarray problem, in which we have a 1 Dimensional array and must find the maximum sum in that subarray. To solve this problem, the most naive approach will be to find all the sub ? arrays, sum their elements, and return the maximum, but the time complexity will be O(N*N). To reduce this there is an algorithm that will reduce the time complexity from O(N*N) to O(N) named as Kadens Algorithm.

In programming, there are algorithms based on the Dynamic programming concept in which the problem is broken into sub ? problems and the result is saved that is used for similar sub ? problem. Kaden's algorithm is also one of the Dynamic programming algorithms which will store the maximum subarray sum till the current index using the previous index.

Algorithm

Step 1: Import the required packages at the top using the import keyword.

Step 2: Then the main function will get run first.

• First, we declare and initialize the array.

• Now we are calling the maxSumSubArray() function in which we are implementing Kaden's algorithm.

Step 3: maxSumSubArray() function implementation

• Initialize the variables named sum and maxSum and initialize with the values 0 and INT_MIN respectively.

• Running for loop for every element of the array. On each iteration

• Adding current index value to variable sum.

• If the condition is to check whether the sum is greater than maxSum or not if yes then we will dp maxSum = sum.

• Another if condition is to check whether the sum is less than zero or not if yes then make sum = 0.

• Return the maxSum value.

Step 4: Print the max sum subarray in the given array that is returned by the maxSumSubArray() function.

Example

Let us find the maximum subarray sum of the array {3, ?3, 4, 2, ?1, 5}

Sum = 0

maxSum = INT_MIN

Iteration 1

At i = 0 array[i] = 3 Sum = 0 + 3 = 3 maxSum < sum maxSum = 3 

Iteration 2

At i = 1 array[i] = ?3 Sum = 3 + (?3) = 0 maxSum > sum maxSum = 3 

Iteration 3

At i = 2 array[i] = 4 Sum = 0 + 4 = 4 maxSum < sum maxSum = 4 

Iteration 4

At i = 3 array[i] = 2 Sum = 4 + 2 = 6 maxSum < sum maxSum = 6 

Iteration 5

At i = 4 array[i] = ?1 Sum = 6 + (?1) = 5 maxSum > sum maxSum = 6 

Iteration 6

At i = 5 array[i] = 5 Sum = 5 + (5) = 10 maxSum < sum maxSum = 10 

Example

In the following example, we will demonstrate how to develop a Golang program that will implement Kaden's algorithm

package main import ( "fmt" "math" ) // function to print the array with array and // size of the array as argument func printArray(array []int, size int) { for i := 0; i < size; i++ { fmt.Print(array[i], " ") } fmt.Println() } func maxSumSubArray(array []int, size int) int { // declaring variable sum of int type // and an iterator i var sum, maxSum, i int // initializing the variables declared above sum = 0 maxSum = math.MinInt i = 0 // running for loop from o to the size of the array for i < size { sum = sum + array[i] if sum > maxSum { maxSum = sum } if sum < 0 { sum = 0 } i++ } return maxSum } func main() { // declaring and initializing the // array of size 6 using the shorthand method array := []int{-2, -3, 4, -1, -2, 1, 5, -3} fmt.Println("Golang program to find the maximum sum subarray in the given array using Kaden's algorithm.") fmt.Print("array: ") printArray(array, len(array)) // calling maxSumSubArray() function by passing array and length as a parameter sum := maxSumSubArray(array, len(array)) fmt.Println("The maximum sum is", sum) } 

Output

Golang program to find the maximum sum subarray in the given array using Kaden's algorithm. array: -2 -3 4 -1 -2 1 5 -3 The maximum sum is 7 

Conclusion

This is the implementation of Kaden's algorithm which is one of the dynamic programming algorithms to find the max sum subarray. To solve such a problem in the interviews in the least time everyone uses Kaden's algorithm. To learn more about Golang you can explore these tutorials.