TikTok 面试真题解析：最大子数组和（Maximum Subarray / Kadane）｜线性 DP 经典题

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:
6Explanation:
The subarray [4,-1,2,1] has the largest sum 6.

这道题是在所有连续子数组里找“和最大”的那个。核心思路是遍历数组时维护一个当前子数组的累计和：如果累计和已经变成负数，那它继续往后加只会拖累后面的结果，因此可以果断从当前位置重新开始。与此同时再维护一个全局最大值即可，整体是一趟扫描就能完成的经典线性 DP（Kadane）思路。