【leetcode hot 100 53】最大子数组和

解法一：（动态规划）我们用 f(i) 代表以第 i 个数末端的「连续子数组的最大和」，那么很显然我们要求的答案就是：max{f(i)}，f(i)=max{f(i−1)+nums,nums}

1. class Solution {
2.     public int maxSubArray(int[] nums) {
3.         int pre=0, max_sum=nums[0], left=0;
4.         while(left<nums.length){
5.             pre=Math.max(pre+nums[left],nums[left]);
6.             max_sum=Math.max(max_sum,pre);
7.             left++;
8.         }
9.         return max_sum;
10.     }
11. }

复制代码

注意：

• ‌动态规划通过将一个大题目分解为多个重叠的子题目，并存储子题目标解以制止重复盘算，从而进步算法服从。其焦点头脑在于“分解题目、缓存中心结果，制止重复盘算，从而高效求解复杂题目”‌
  
• 类似【leetcode hot 100 560】和为K的子数组