Go Leetcode: Max Two Sub Slices Sum

Posted on Edited on In

Problem

Given a slice a. There are 2 sub slices. One’s length is k, the other’s is p.
These 2 sub slices are not overlaid. Find the max sum of the 2 sub slices.

Return -1 if can’t find one.

Example 1:

1
2
Input: [1,3,4,7,5,8,2,9], 3, 2
Output: 35

Example 2:

1
2
Input: [1,3,4,7,5,8], 100, 2
Output: -1

Thought

Move slice K through A, at the left and right side of K place the slice P.
To improve the efficiency, store sums of K and P in hash tables.


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
func maxSum(a []int, k, p int) int {
	if k+p > len(a) {
		return -1
	}
	kt := hashTable(a, k)
	pt := hashTable(a, p)
	ki := 0
	for ki < len(kt) {
		left := maxVal(pt[:max(0, ki-p+1)]...)
		right := maxVal(pt[min(ki+k, len(pt)):]...)

		if left == -1 && right == -1 {
			kt[ki] = -1
		} else {
			kt[ki] = kt[ki] + max(right, left)
		}
		ki++
	}

	return maxVal(kt...)
}

func hashTable(a []int, length int) []int {
  if length > len(a) {
		return []int{}
	}
	tlen := len(a) - length + 1
	t := make([]int, tlen)
	i := 0
	for i < tlen {
		t[i] = sum(a[i : i+length]...)
		i++
	}
	return t
}

func maxVal(nums ...int) int {
	m := -1
	for _, v := range nums {
		if m < v {
			m = v
		}
	}
	return m
}

func sum(nums ...int) int {
	res := 0
	for _, n := range nums {
		res += n
	}
	return res
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}