53.最大子数组和
- 题目描述
- 暴力法思路
- 暴力法代码
- 动态规划思路
- 动态规划代码
题目描述
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例一:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例二:
输入:nums = [1]
输出:1
示例三:
输入:nums = [5,4,-1,7,8]
输出:23
暴力法思路
暴力法就没什么好说的了,直接双循环暴力解即可
暴力法代码
class Solution {
public int maxSubArray(int[] nums) {
//java中赋值int最小值
int max = Integer.MIN_VALUE;
for(int i = 0;i<nums.length;i++){
int sum = 0;
for(int j = i;j<nums.length;j++){
sum+=nums[j];
if(sum>max)
max = sum;
}
}
return max;
}
}
动态规划思路
用dp来表示以当前数组元素结尾的最大连续子数组和,我们只需遍历数组,找到这个最大的dp即可,怎么找呢?我们假设dp的初始值是nums[0],因为第一个元素结尾的最大连续子数组和一定是第一个数本身,从第二个数开始,dp就等于之前的dp+当前的数或者当前的数本身,我们取其中大的即可。用max保存最大的dp,返回max即可。
动态规划代码
class Solution {
public int maxSubArray(int[] nums) {
//初始化dp,max初值等于nums[0]
int dp = nums[0];
int max = dp;
for(int i = 1;i<nums.length;i++){
dp = Math.max(dp+nums[i],nums[i]);
max = Math.max(max,dp);
}
return max;
}
}