Maximum subarray problem with some recommended testcase in Go.

maxsum.go

package maxsum

import "math"

func MaxSum1(v []float64) (maxSofar float64) {
	length := len(v)
	for i := 0; i < length; i++ {
		for j := i; j < length; j++ {
			sum := 0.0
			// sum of [i..j]
			for k := i; k <= j; k++ {
				sum += v[k]
			}
			maxSofar = math.Max(maxSofar, sum)
		}
	}
	return
}

func MaxSum2(v []float64) (maxSofar float64) {
	length := len(v)
	for i := 0; i < length; i++ {
		sum := 0.0
		for j := i; j < length; j++ {
			// sum of [i..j]
			sum += v[j]
			maxSofar = math.Max(maxSofar, sum)
		}
	}
	return
}

func MaxSum2b(v []float64) (maxSofar float64) {
	length := len(v)
	// length+1 avoid sumArray[-1]
	sumArray := make([]float64, length+1)
	for i := 0; i < length; i++ {
		sumArray[i+1] = sumArray[i] + v[i]
	}

	for i := 0; i < length; i++ {
		for j := i; j < length; j++ {
			maxSofar = math.Max(maxSofar, sumArray[j+1]-sumArray[i])
		}
	}

	return
}

// ma, mb, mc
func maxSum(v []float64, low, high int) float64 {
	if low > high { // zero elements
		return 0
	}
	if low == high { // one element
		return math.Max(0, v[low])
	}

	middle := (low + high) / 2
	// find max crossing to left
	lmax, sum := 0.0, 0.0
	for i := middle; i >= low; i-- {
		sum += v[i]
		lmax = math.Max(lmax, sum)
	}

	// find max crossing to right
	rmax, sum := 0.0, 0.0
	for i := middle + 1; i <= high; i++ {
		sum += v[i]
		rmax = math.Max(rmax, sum)
	}

	mc := lmax + rmax

	// recusively left && right
	maxNow := math.Max(maxSum(v, low, middle), maxSum(v, middle+1, high))
	maxNow = math.Max(maxNow, mc)

	return maxNow
}

func MaxSum3(v []float64) (maxSofar float64) {
	return maxSum(v, 0, len(v)-1)
}

// MaxSumSuite.BenchmarkMaxSum	      20	  96768717 ns/op
func MaxSum4(v []float64) (maxSofar float64) {
	maxHere := 0.0
	for length, i := len(v), 0; i < length; i++ {
		maxHere = math.Max(maxHere+v[i], 0)
		maxSofar = math.Max(maxSofar, maxHere)
	}
	return
}

var MaxSum = MaxSum4

maxsum_test.go

package maxsum

import (
	"math/rand"
	"testing"
	"time"

	check "gopkg.in/check.v1"
)

// define a test suite
type MaxSumSuite struct{ input []float64 }

// registe test suite
func init() { check.Suite(&MaxSumSuite{}) }

// make `go test` happy
func TestMe(t *testing.T) { check.TestingT(t) }

func (s *MaxSumSuite) Comment() check.CommentInterface {
	return check.Commentf("%+v", s.input)
}

func (s *MaxSumSuite) SimpleTest(c *check.C, output float64) {
	c.Check(MaxSum(s.input), check.Equals, output, s.Comment())
}

// 冒烟测试
func (s *MaxSumSuite) TestSmoke(c *check.C) {
	s.input = []float64{31, -41, 59, 26, -53, 58, 97, -93, -23, 84}
	s.SimpleTest(c, 187)
}

// 边界测试
func (s *MaxSumSuite) TestBoundary(c *check.C) {
	s.input = []float64{}
	s.SimpleTest(c, 0)

	s.input = []float64{-42}
	s.SimpleTest(c, 0)

	s.input = []float64{42}
	s.SimpleTest(c, 42)

	s.input = []float64{-1, -2, -3}
	s.SimpleTest(c, 0)

	s.input = []float64{1, 2, 3, 4, 5}
	s.SimpleTest(c, 15)
}

// 随机测试
func (s *MaxSumSuite) TestRandom(c *check.C) {
	maxSize, testCount := 100, 1000
	// test count N
	for i := 0; i < testCount; i++ {
		// random input (size)
		size := rand.Intn(maxSize)
		s.input = make([]float64, size)
		for j := 0; j < size; j++ {
			s.input[j] = rand.NormFloat64() * 100000
		}

		// check output
		// float64 equal -> int64 equal
		c.Check(int64(MaxSum(s.input)), check.Equals, int64(MaxSum1(s.input)), s.Comment())
		c.Check(int64(MaxSum(s.input)), check.Equals, int64(MaxSum2(s.input)), s.Comment())
		c.Check(int64(MaxSum(s.input)), check.Equals, int64(MaxSum2b(s.input)), s.Comment())
	}

	rand.Seed(time.Now().UnixNano())
	rand.NormFloat64()
}

// 性能测试
func (s *MaxSumSuite) BenchmarkMaxSum(c *check.C) {}