...

/

Solution Review: Finding the Largest Sum Subarray

Solution Review: Finding the Largest Sum Subarray

Let’s take a detailed look at the previous challenge’s solution.

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

Press + to interact
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 ...