Kadane’s Algorithm in Go

Kadane’s Algorithm is used to find the subarray with the largest sum in a given array of integers. This algorithm operates in O(n) time complexity, making it very efficient for this problem.

Algorithm Explanation

The idea behind Kadane’s Algorithm is to iterate through the array while keeping track of the maximum sum of the subarray that ends at the current position. This is achieved using two variables:

• currentMax: The maximum sum of the subarray that ends at the current position.
• globalMax: The maximum sum of any subarray found so far.

For each element in the array, we update currentMax as the maximum of the current element and the sum of the current element and the previous currentMax. Then, we update globalMax as the maximum of globalMax and currentMax.

Go Code Implementation

// Package main provides the Kadane's Algorithm implementation in Go
package main

import (
	"fmt"
)

// Function to find the subarray with the largest sum
func findMaxSubarraySum(nums []int) int {
	// Initialize currentMax and globalMax with the first element of the array
	currentMax := nums[0]
	globalMax := nums[0]

	// Iterate through the array starting from the second element
	for _, num := range nums[1:] {
		// Update currentMax to the maximum of the current element and the sum of current element and currentMax
		if num > currentMax+num {
			currentMax = num
		} else {
			currentMax += num
		}

		// Update globalMax if currentMax is greater than globalMax
		if currentMax > globalMax {
			globalMax = currentMax
		}
	}

	// Return the globalMax which is the largest sum of subarray found
	return globalMax
}

// Main function to test the algorithm
func main() {
	// Example array
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}

	// Find and print the maximum subarray sum
	maxSubarraySum := findMaxSubarraySum(nums)
	fmt.Println("The maximum subarray sum is:", maxSubarraySum)
}

Explanation of the Go Code

In the Go code above:

• The function findMaxSubarraySum takes a slice of integers as input and returns the sum of the subarray with the largest sum.
• We initialize currentMax and globalMax with the first element of the slice.
• We iterate through the slice starting from the second element. For each element, we update currentMax and then globalMax if necessary.
• The main function provides an example slice and calls the findMaxSubarraySum function to find and print the maximum subarray sum.

Output

For the example slice {-2, 1, -3, 4, -1, 2, 1, -5, 4}, the output will be:

The maximum subarray sum is: 6

The subarray with the largest sum is {4, -1, 2, 1} which sums to 6.