以下是 LeetCode 2551「将珠子放入背包中」的 Python3 实现。

解题思路

· 总得分 = weights[0] + weights[-1] + 所有选中的 weights[i] + weights[i+1]（其中 i 为切割点）。
· 需要选择恰好 k-1 个切割点，总得分 = 固定部分 + 所选 pairSum 之和。
· 最大化总得分 → 选最大的 k-1 个 pairSum。
· 最小化总得分 → 选最小的 k-1 个 pairSum。
· 差值 = (最大 k-1 个之和) - (最小 k-1 个之和)。
· 特判 k == 1 或 k == n 时，差值为 0。

```python
class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        n = len(weights)
        if k == 1 or k == n:
            return 0
        
        # 计算相邻两数之和
        pair_sums = [weights[i] + weights[i + 1] for i in range(n - 1)]
        pair_sums.sort()
        
        # 取最小的 k-1 个和最大的 k-1 个
        min_sum = sum(pair_sums[:k - 1])
        max_sum = sum(pair_sums[-(k - 1):])
        
        return max_sum - min_sum
```

复杂度分析

· 时间复杂度：O(n log n)，排序为主。
· 空间复杂度：O(n)，用于存储相邻和。