6331The most prizes won in the two lines make()usage

topic

6331. The most prizes won in the two lines

Thought

make
make() yes Go Built -in function of language memory distribution，There are three parameters default。

make(Type, len, cap)

Type：type of data，Necessary parameters，Type 的值只能yes slice、 map、 channel 这三种type of data。
len：type of data实际占用的内存空间长度，map、 channel yesOptional parameter，slice yesNecessary parameters。
cap：为type of data提前预留的内存空间长度，Optional parameter。
所谓的提前预留yes当前为type of data申请内存空间的时候，Apply for additional memory space in advance，This can avoid the overhead brought by the second allocation of memory，Greatly improve the performance of the program。
You have such doubts when you see here，Since the size of the data has been specified at the time of initialization，Then why do you still specify the reserved size?？
这yes因为 make() 使用的yes一种动态数组算法，At first apply to the operating system for a small piece of memory，
这个就yes cap，wait cap quilt len After the occupation is full, you need to expand the capacity，
扩容就yes动态数组再去向操作系统申请当前长度的两倍的内存，Then copy the old data to the new memory space。

func maximizeWin(prizePositions []int, k int) (ans int) {
	n := len(prizePositions)
	pre := make([]int, n+1)
	left := 0
	for right, v := range prizePositions {
		for v-prizePositions[left] > k {
			left++
		}
		ans = max(ans, right-left+1+pre[left])
		pre[right+1] = max(pre[right],right-left+1)
	}
	return ans
}

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