【leetcodehot10053】最大子数组和

解法一：（动态规划）我们用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：max{f(i)}，f(i)=max{f(i−1)+nums[i],nums[i]} class Solution { public int maxSubArray(int[] nums) { int pre=0, max_sum=nums[0], left=0; while(left<nums.length){ pre=Math.max(pre+nums[left],nums[left]); max_sum=Math.max(max_sum,pre); left++; } return max_sum; } } 注意： ‌动态规划通过将一个大问题分解为多个重叠的子问题，并存储子问题的解以避免重复计算，从而提高算法效率。其核心思想在于“分解问题、缓存中间结果，避免重复计算，从而高效求解复杂问题”‌