将珠子放入背包中

题目描述

你有 $k$ 个背包。给你一个下标从 0  开始的长度为 $n$ 整数数组 $weights$ ，其中 $weights[i]$ 是第 $i$ 个珠子的重量。同时给你整数 $k$ 。

请你按照如下规则将所有的珠子放进 $k$ 个背包。

• 没有背包是空的。
• 如果第 $i$ 个珠子和第 $j$ 个珠子在同一个背包里，那么下标在 $i$ 到 $j$ 之间的所有珠子都必须在这同一个背包中。
• 如果一个背包有下标从 $i$ 到 $j$ 的所有珠子，那么这个背包的价格是 $weights[i] + weights[j]$ 。

一个珠子分配方案的 分数  是所有 $k$ 个背包的价格之和。

请你返回所有分配方案中， 最大分数  与 最小分数  的 差值  为多少。

输入格式

第一行两个空格隔开的整数 $n$ $k$；

第二行 $n$ 个空格隔开的整数表示 $weights$ 数组的元素。

输出格式

一行一个整数表示答案。

示例 1：

4 2
1 3 5 1

4

解释:

分配方案 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6 。 分配方案 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10 。 所以差值为 10 - 6 = 4 。

示例 2：

2 2
1 3

0

解释: 唯一的分配方案为 [1],[3] 。 最大最小得分相等，所以返回 0 。

提示：

• $1 <= k <= weights.length <= 10^5$
• $1 <= weights[i] <= 10^9$