maxsubarray

maxsubarray.go

package main

import "fmt"

/*
{
    int arr[] = { 2, 3, 4, 5, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    printf("Maximum contiguous sum is %d\n", max_sum);
    getchar();
    return 0;
}
*/

// A utility function to find maximum of two integers
func max(a, b int) int { 
 if a > b{
 return a
}
return b 
 }
 
// A utility function to find maximum of three integers
func max3(a, b, c int )int { return max(max(a, b), c) }

func maxcrosssum(arr []int,low,mid,high int)(int){
	sum := 0;
    left_sum := -100000;
    for i := mid; i >= low; i-- {
        sum = sum + arr[i]
        if sum > left_sum{
            left_sum = sum
}
    }
 
    // Include elements on right of mid
    sum = 0;
    right_sum := -1000000;
    for i := mid + 1; i <= high; i++ {
        sum = sum + arr[i]
        if sum > right_sum{
            right_sum = sum
}
    }
 
    // Return sum of elements on left and right of mid
    // returning only left_sum + right_sum will fail for
    // [-2, 1]
    return max3(left_sum + right_sum, left_sum, right_sum)

}

func maxsubarray(arr []int,l,h int)int{

    // Base Case: Only one element
    if l == h{
        return arr[l]
}
 
    // Find middle point
    m := (l + h) / 2;
 
    /* Return maximum of following three possible cases
            a) Maximum subarray sum in left half
            b) Maximum subarray sum in right half
            c) Maximum subarray sum such that the subarray
       crosses the midpoint */
    return max3(maxsubarray(arr, l, m),
               maxsubarray(arr, m + 1, h),
               maxcrosssum(arr, l, m, h));
}

func Onmaxsumarray(a []int)int{

n := len(a)
ms := -1000000
msf := 0
for i:=0;i<n;i++{
msf = a[i]+msf
if msf > ms{
	ms = msf
}
if msf <0{
msf = 0
}
}
return ms
}

func main() {
	a := []int{-2, -3, 4, -1, -2, 1, 5, -3}
	fmt.Println(maxsubarray(a[:],0,7))
	fmt.Println(Onmaxsumarray(a))
}