最大化分割得分的平方和（问题求解）
原文英文，约1000词，阅读约需4分钟。
📝
内容提要
给定一个整数列表和一个整数k，要求将列表分成k个连续非空部分，以最大化分割得分。得分为每部分和的平方之和。可以使用前缀和和动态规划的方法求解，时间复杂度为O(k × n log n)。
🔎
延伸解读
动态规划的应用
本文中使用动态规划来解决分割问题，定义状态dp[j][i]表示将前i个元素分成j部分的最大得分。这种方法有效地减少了计算复杂度，使得在处理大规模数据时依然高效。
前缀和的优势
通过使用前缀和，能够在常数时间内快速计算任意连续区间的和。这一技巧在动态规划中至关重要，尤其是在需要频繁计算区间和的情况下，显著提高了算法的效率。
Li Chao树的应用
Li Chao树用于优化动态规划中的最大值查询，能够在对数时间内插入和查询线性函数。这种数据结构的使用，使得每层DP的复杂度降低，整体时间复杂度达到O(k × n log n)，适合处理大规模数据。
❓
Q&A
如何将整数列表分成k个部分以最大化得分？
将列表分成k个连续非空部分，得分为每部分和的平方之和，使用动态规划和前缀和来计算。
这个问题的时间复杂度是多少？
时间复杂度为O(k × n log n)。
如何处理负数和正数的情况？
算法能够处理负数和正数，确保计算每部分和的平方时不受负数影响。
动态规划的状态定义是什么？
dp[j][i]表示将前i个元素分成j部分的最大得分。
示例输入和输出是什么？
输入为5 2和列表[1, 2, -1, 2, 3]，输出为29。
如何加速动态规划的计算？
使用线性容器技巧和Li Chao树来加速计算，降低每层DP的复杂度。
🏷️
