Google 面试题复盘：最大子数组分数，如何从 O(N²) 优化到 O(N)？

Google 面试遇到的两道连续子数组题。第一问求最大分数，第二问在同一算法上返回对应的左右下标。
题目给定一个整数数组，连续子数组的分数定义为：
首元素 + 尾元素 - 中间元素之和
子数组长度至少为 2。
关键是先把公式变形
设子数组左右下标为 L 和 R，定义前缀和 S[i] 为下标 i 之前所有元素之和，那么：
中间元素之和 = S[R] - S[L + 1]
因此，分数可以改写为：
nums[L] + nums[R] - S[R] + S[L + 1]
而 S[L + 1] = S[L] + nums[L]，所以：
score(L, R) = (2 × nums[L] + S[L]) + (nums[R] - S[R])
现在公式分成了两部分：左边只依赖 L，右边只依赖 R。
固定右边界 R 时，只需要知道之前所有合法

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

，按题目约定，第一问返回 0，第二问返回空列表。
max_score 要初始化为负无穷。这样当所有分数都为负时，仍能选出真实子数组，而不会错误返回 0。
两问的时间复杂度都是 O(N)，额外空间 O(1)。记录左右下标不会改变渐进复杂度。
提供技术岗位 VO 面试支持，覆盖 Coding、System Design、Behavioral / BQ 和 Project Deep Dive 等环节。