DEV Community
·
689. 三个不重叠子数组的最大和
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个整数数组和一个整数k，寻找三个不重叠的长度为k的子数组，使其和最大，并返回每个子数组的起始索引。如果有多个答案，返回字典序最小的。使用动态规划和滑动窗口技术，确保时间复杂度为O(n)。
🎯
关键要点
- 给定一个整数数组和一个整数k，寻找三个不重叠的长度为k的子数组，使其和最大。
- 返回每个子数组的起始索引，如果有多个答案，返回字典序最小的。
- 使用动态规划和滑动窗口技术，确保时间复杂度为O(n)。
- 首先计算所有长度为k的子数组的和，使用滑动窗口技术高效完成。
- 创建两个辅助数组left和right，分别存储当前索引之前和之后的最佳子数组索引。
- 对于每个可能的中间子数组，计算总和并更新结果。
- 通过从左到右的迭代，确保返回字典序最小的答案。
➡️
