Waymo OA 面试真题解析：双端取数最大得分 / 动态规划

You have an array containing N elements, and each element has a score. In each step, you can pop an element from the leftmost or the rightmost position of the array, and gain the score of the element you choose. What is the maximum aggregated score you can obtain after K steps?

You have another array M with K weights. Each time you make the i-th pop, multiply the score of the chosen element by the weight in M[i]. What is the maximum score you can get?

这道题考察的是从数组两端取数的最优决策。第一问通常可以用前缀和或枚举“从左取几个、从右取几个”的方式，在 K 步内找到最大总分；第二问加入了每一步不同的权重后，问题升级为带顺序约束的动态规划，需要记录在处理到某一步时，左侧和右侧分别取了多少个元素，进而计算当前选择的最大收益。核心思路是利用区间边界变化很小这一性质，把暴力搜索优化为 DP 或枚举组合，适合考察状态设计与转移能力。