max Subarray Sum Algorithm

This problem can be solved use several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is allowed). The maximal subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximal likelihood estimate of shapes in digitized pictures. 

There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximal subarray problem in O(n3−ε) time, for any ε>0, would imply a similarly fast algorithm for the all-pairs shortest paths problem. Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time, better the brute force working time of O(n3).
/* O(n) solution, for calculating 
maximum contiguous sum in the given array. */

package main

import (
	"fmt"
)

func Max(x int, y int) int {
    if x < y {
        return y
    }
    return x
}

func maxSubarraySum(array []int) int {
    var currentMax int = 0
    var maxTillNow int = 0
	for _,v :=range array{
	    currentMax = Max(v, currentMax + v)
	    maxTillNow = Max(maxTillNow, currentMax)
	}
	return maxTillNow
}

func main() {
	array := []int{-2, -5, 6, 0, -2, 0, -3, 1, 0, 5, -6}
	fmt.Println("Maximum contiguous sum: ",  maxSubarraySum(array))
}

LANGUAGE:

DARK MODE: