MaxSubNonNegativesArray

max_set.go

// Given an array of integers, A of length N, find out the maximum sum sub-array of non negative numbers from A.
/**
 * @input A : Integer array
 * 
 * @Output Integer array.
 */
package main

import "fmt"

func chooseMax(subArr1 []int, max1 int, subArr2 []int, max2 int) (maxArr[]int, max int) {
    if (max2 > max1) || (max1 == max2 && len(subArr2) > len(subArr1)) {
        maxArr = subArr2
        max    = max2
    } else {
        maxArr = subArr1
        max    = max1
    }

    return
}

func maxSet(A []int )  ([]int) {
    maxSubArr := []int{}
    max       := 0
    
    currSubArr := []int{}
    currMax    := 0

    for _, v := range A {
        if v < 0 {
            // subarr ends

            maxSubArr, max = chooseMax(maxSubArr, max, currSubArr, currMax)
            
            currSubArr = nil
            currMax    = 0 
            
        } else {
            // subarr continues
            currSubArr = append(currSubArr, v)
            currMax += v
        }
    }
    
    maxSubArr, max = chooseMax(maxSubArr, max, currSubArr, currMax)
    
    return maxSubArr
}

func main() {
  fmt.Println(maxSet([]int{0, 0, -1, 0}))
}