LeetCode Hot100 53.最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

53. 最大子数组和 – 力扣（LeetCode）

思路

动态规划，维护一个变量pre记录遍历数组到此刻时的最大子数组和，如果num+pre<num，那么从num重新开始一个子数组

考虑到子数组中可能有负数，初始化max=nums[0]

代码

class Solution {
public int maxSubArray(int[] nums) {
int max=nums[0];
int pre=0;
for(int num:nums){
pre=Math.max(num,pre+num);
max=Math.max(max,pre);
}
return max;
}
}