Solution Review: Finding the Largest Sum Subarray
Let’s take a detailed look at the previous challenge’s solution.
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
Press + to interact
package mainimport ("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 correctlymaxSoFar := data[0]maxEndingHere := data[0]// Loop through the array starting from the second elementfor 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 elementmaxEndingHere = maxEndingHere + data[i]// Reset if current element is better on its ownif maxEndingHere < data[i] {maxEndingHere = data[i]}// Update maxSoFar if we found a new maximum subarray sumif maxSoFar < maxEndingHere {maxSoFar = maxEndingHere}}// Return the maximum subarray sum foundreturn maxSoFar}//Testing codefunc 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 ...