找客源免费用哪个软件好_软件商店2023_seo服务外包报价_如何让百度能查到自己

解法一：（动态规划）我们用 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;}
}

注意：

• ‌动态规划通过将一个大问题分解为多个重叠的子问题，并存储子问题的解以避免重复计算，从而提高算法效率。其核心思想在于“分解问题、缓存中间结果，避免重复计算，从而高效求解复杂问题”‌