maximum subarray


See On Github

Data

Contributor

Generic placeholder thumbnail

by jcla1

in go

Tags

Source Code

package kadane

func MaxSubarray(arr []int) int {
	if len(arr) < 1 {
		return 0
	}

	currentMax, maxSoFar := arr[0], arr[0]

	for _, v := range arr[1:] {
		currentMax = max(currentMax+v, v)
		maxSoFar = max(currentMax, maxSoFar)
	}

	return maxSoFar
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}
package kadane

import "testing"

func TestMaxSubarray(t *testing.T) {
	arrs := [][]int{[]int{-2, 1, -3, 4, -1, 2, 1, -5, 4}, []int{2, 3, 7, -5, -1, 4, -10}}
	expectedResults := []int{6, 12}

	var result int

	for i, expected := range expectedResults {
		result = MaxSubarray(arrs[i])
		if result != expected {
			t.Errorf("MaxSubarray(%v) = %d, want %d", arrs[i], result, expected)
		}
	}
}

func TestMax(t *testing.T) {
	a := []int{1, 5, 0, -1, 10}
	b := []int{1, 4, 0, 10, -1}
	expectedResults := []int{1, 5, 0, 10, 10}

	var result int

	for i, expected := range expectedResults {
		result = max(a[i], b[i])
		if result != expected {
			t.Errorf("max(%d, %d) = %d, want %d", a[i], b[i], result, expected)
		}
	}
}