- 题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分
- 思路：定义一个dp数组，用于存放从第0个元素到i个元素的最大子数组的最大值；
- 遍历nums数组，使得dp[i]中的每一个元素均有值，其值代表着从第0个元素到i个元素的最大子数组的最大值；
- 实现dp[i]存放着从第0个元素到i个元素的最大子数组的最大值的方法，使dp[i-1]+nums[i]与nums[i]比较，取最大值；即从第0个元素到i-1个元素的最大子数组的最大值加上nums数组第i个元素 与 nums的第一个元素相比，取最大值。
- 遍历dp数组取最大值即为所求的结果。
class Solution {
public int maxSubArray(int[] nums) {
//定义数组的长度
int n = nums.length;
if(n==0) return 0;
//定义一个dp数组，用于存放从第0个元素到i个元素的最大子数组的最大值
nt[] dp = new int[n];
dp[0] = nums[0];
//遍历整个nums数组，使得dp[i]数组的每个元素均有值
for(int i = 1;i
dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);
}
int res = Integer.MIN_VALUE;
for(int i =0 ;i
res = Math.max(res,dp[i]);
}
return res;
}
}
解法二：
class Solution {
public int maxSubArray(int[] nums) {
//定义数组的长度
int n = nums.length;
if(n==0) return 0;
//定义一个dp数组，用于存放从第0个元素到i个元素的最大子数组的最大值
int dp_0 =nums[0];
int dp_1 = 0;
int res = dp_0;
for(int i = 1;i
dp_1 = Math.max(nums[i],nums[i]+dp_0);
dp_0 = dp_1;
//后面的结果可能会比前面小，所以一直求结果的最大值
res = Math.max(res,dp_0);
}
return res;
}
}
