LeetCode 53. 最大子数组和经典Kadane 算法。思路维护两个变量current_sum以当前元素结尾的子数组最大和max_sum全局最大子数组和状态转移current_sum max(num, current_sum num)如果current_sum为负数则从当前元素重新开始累加更优。Rust 实现implSolution{pubfnmax_sub_array(nums:Veci32)-i32{letmutmax_sumnums[0];letmutcurrent_sumnums[0];fornuminnums.iter().skip(1){// 当前和为负则丢弃从当前元素重新开始current_sumnum.max(current_sumnum);// 更新全局最大值max_summax_sum.max(current_sum);}max_sum}}复杂度时间复杂度O(n)空间复杂度O(1)关键点current_sum num.max(current_sum num)是核心判断是「重新开始」还是「继续累加」更优初始化用nums[0]避免单独处理第一个元素遍历从第二个元素开始skip(1)
Kimi LeetCode 53. 最大子数组和 Rust实现
LeetCode 53. 最大子数组和经典Kadane 算法。思路维护两个变量current_sum以当前元素结尾的子数组最大和max_sum全局最大子数组和状态转移current_sum max(num, current_sum num)如果current_sum为负数则从当前元素重新开始累加更优。Rust 实现implSolution{pubfnmax_sub_array(nums:Veci32)-i32{letmutmax_sumnums[0];letmutcurrent_sumnums[0];fornuminnums.iter().skip(1){// 当前和为负则丢弃从当前元素重新开始current_sumnum.max(current_sumnum);// 更新全局最大值max_summax_sum.max(current_sum);}max_sum}}复杂度时间复杂度O(n)空间复杂度O(1)关键点current_sum num.max(current_sum num)是核心判断是「重新开始」还是「继续累加」更优初始化用nums[0]避免单独处理第一个元素遍历从第二个元素开始skip(1)