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
These are two classic array interview problems. Maximum Subarray is typically solved with Kadane's algorithm by tracking the best subarray sum ending at each position and the global maximum in O(n) time. Largest Rectangle in Histogram is usually solved with a monotonic stack to find the nearest smaller bar on both sides and compute the maximum rectangle area in linear time as well. Together, they test core skills in one-pass scanning, boundary handling, and stack-based optimization.
