max sequence sum in go

To find the maximum sum of a subsequence in an array or slice, you can use the Kadane's algorithm which is an efficient dynamic programming approach for solving this problem.

Here is the implementation of Kadane's algorithm in Go:

main.go
func maxSubArraySum(arr []int) int {
    maxSoFar := arr[0]
    maxEndingHere := arr[0]

    for i := 1; i < len(arr); i++ {
        maxEndingHere = max(arr[i], maxEndingHere+arr[i])
        maxSoFar = max(maxSoFar, maxEndingHere)
    }

    return maxSoFar
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
339 chars
19 lines

The maxSubArraySum function takes an array of integers as input and returns the maximum sum of a subsequence in the array. The max function is a helper function that returns the maximum of two integers.

The algorithm works by iterating over the array and keeping track of the maximum sum seen so far (maxSoFar) and the maximum sum ending at the current position (maxEndingHere). At each iteration, maxEndingHere is updated by either adding the current element or starting a new subsequence from the current element. maxSoFar is also updated at each iteration with the maximum value seen so far.

Finally, maxSoFar is returned as the maximum sum of a subsequence in the array.

Here is an example usage of the function:

main.go
arr := []int{1, -2, 3, 4, -1, 2, -3}
fmt.Println(maxSubArraySum(arr)) // Output: 8
83 chars
3 lines

In this example, the maximum sum of a subsequence in the array is 8 which corresponds to the subsequence [3, 4, -1, 2].