Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Largest Rectangle in Histogram
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Input: heights = [2,1,5,6,2,3]
Output: 10
这组题目考察的是经典数组与栈的基础能力。Maximum Subarray 通常用 Kadane 算法，在遍历过程中维护“以当前位置结尾的最大子数组和”和全局最大值，时间复杂度为 O(n)。Largest Rectangle in Histogram 则需要借助单调栈，快速找到每个柱子左右第一个更矮的位置，从而计算以该柱子为高度时能形成的最大矩形面积，整体也是 O(n)。这两题都非常适合用于检验面试中对线性扫描、边界处理和单调数据结构的掌握。
正文完
