Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Finding the Largest Sum Subarray

Understand how to find the largest sum subarray in an array using a single-pass dynamic programming method. Learn to track current and global maximum sums, update subarrays effectively, and implement this efficient O(n) solution in Go.

We'll cover the following...

Solution

  • In a single scan, we find the maximum subarray sum using a dynamic approach. We keep track of:

    • The current maximum sum ending at each element.
    • The global maximum sum seen so far.

  • If the current maximum becomes greater than the global maximum, we update the global value.

  • Finally, we return the global maximum sum.

Solution Code

Go (1.6.2)
package main
import (
    "fmt"
    "strings"
)
func MaxSubArraySum(data []int) int {
    size := len(data)
    // Initialize maxSoFar and maxEndingHere with the first element of the array
    // This helps handle arrays with all negative numbers correctly
    maxSoFar := data[0]    
    maxEndingHere := data[0]
    // Loop through the array starting from the second element
    for i := 1; i < size; i++ {
        // Decide whether to:
        // - continue the current subarray (add current element to maxEndingHere), or
        // - start a new subarray from the current element
        maxEndingHere = maxEndingHere + data[i]  
        
        // Reset if current element is better on its own
        if maxEndingHere < data[i] {            
            maxEndingHere = data[i]
        }
        
        // Update maxSoFar if we found a new maximum subarray sum
        if maxSoFar < maxEndingHere {  
            maxSoFar = maxEndingHere
        }
    }
    
    // Return the maximum subarray sum found
    return maxSoFar
}
//Testing code
func main() {
    data := []int{1, -2, 3, 4, -4, 6, -14, 6, 2}
    fmt.Print("Max sub array sum for the input [", intSliceToString(data))
    fmt.Println("] is", MaxSubArraySum(data), ".")
}

Time complexity

The time complexity of this algorithm is ...