sum k to max even

sumKToMaxEven_test.go

package main

import (
	"reflect"
	"sort"
	"testing"
)

func TestMaxEvenSum(t *testing.T) {
	for _, testcase := range []struct {
		nums         []int
		k            int
		expectResult []int
		expectSum    int
	}{
		{
			[]int{4, 9, 8, 2, 6},
			3,
			[]int{4, 6, 8},
			18,
		},
		{
			[]int{5, 6, 3, 4, 2},
			5,
			[]int{5, 6, 3, 4, 2},
			20,
		},
		{
			[]int{7, 7, 7, 7, 7},
			1,
			nil,
			-1,
		},
		{
			[]int{10000},
			2,
			nil,
			-1,
		},
		{
			[]int{2, 3, 3, 5, 5},
			3,
			[]int{2, 5, 5},
			12,
		},
	} {
		t.Log(testcase)
		result, sum := maxEvenSum(testcase.nums, testcase.k)
		sort.Ints(result)
		sort.Ints(testcase.expectResult)
		if !reflect.DeepEqual(result, testcase.expectResult) {
			t.Errorf("testcase.expectResult != result")
		}
		if testcase.expectSum != sum {
			t.Errorf("testcase.expectSum != sum")
		}
	}
}

func maxEvenSum(nums []int, k int) (result []int, sum int) {
	if k > len(nums) {
		return nil, -1
	}

	// 奇偶数组
	var odds []int
	var evens []int
	for _, num := range nums {
		switch num % 2 {
		case 0:
			evens = append(evens, num)
		case 1:
			odds = append(odds, num)
		}
	}

	// 逆序排序
	sort.Sort(sort.Reverse(sort.IntSlice(odds)))
	sort.Sort(sort.Reverse(sort.IntSlice(evens)))

	// 如果 k 是奇数，那么一定包含至少一个偶数，否则 奇数 * 奇数 = 奇数，那么 evens[0] 肯定在内（因为最大值）
	// 并且转换成为，求剩下 k - 1 个最大偶数和
	even0 := -1
	if k%2 != 0 {
		if len(evens) == 0 {
			return nil, -1
		}
		even0 = evens[0]
		evens = evens[1:]
		k = k - 1
	}

	// 这时候 k 一定是偶数
	// 选取最大偶数个 奇数数组，剩下的来自偶数数组
	m := len(odds) - len(odds)%2
	if m > k {
		m = k
	}
	n := k - m

	// 在选取最大长度奇数数组情况下，偶数数组个数不足，那么肯定没有结果
	if n > len(evens) {
		return nil, -1
	}

	// 现在有 m 个奇数数组，n 个偶数数组，算出总和，同时 m，n 分别都是偶数
	for i := 0; i < m; i++ {
		sum = sum + odds[i]
	}
	for i := 0; i < n; i++ {
		sum = sum + evens[i]
	}

	// 奇数数组从最右往左，两个取出；偶数数组从最左往右，两个取出；对比各自和，如果能增加，那么修改 m, n，增加 sum 值
	if m >= 2 && n+2 <= len(evens) {
		if (odds[m-1] + odds[m-2]) >= (evens[n] + evens[n+1]) {
			// 已经得到想要的结果
			goto L
		}
		m = m - 2
		n = n + 2
	}
L:
	sum = 0
	for i := 0; i < m; i++ {
		result = append(result, odds[i])
		sum = sum + odds[i]
	}
	for i := 0; i < n; i++ {
		result = append(result, evens[i])
		sum = sum + evens[i]
	}
	if even0 != -1 {
		result = append(result, even0)
		sum = sum + even0
	}
	return
}