最大子数组和-前缀和/动态规划/分治/暴力-Java/c++
一、题目描述
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
二、思路解析
1.前缀和
2.动态规划思想
题目只是要求一个结果,没有说列出来具体的值。
3.分治思想
分治法的思路是这样的,其实也是分类讨论。
连续子序列的最大和主要由这三部分子区间里元素的最大和得到:
第 1 部分:子区间 [left, mid];
第 2 部分:子区间 [mid + 1, right];
第 3 部分:包含子区间 [mid , mid + 1] 的子区间,即 nums[mid] 与 nums[mid + 1] 一定会被选取。
对这三个部分求最大值即可。
4.暴力法
三、代码
1Java前缀和
public int maxSubArray(int[] nums) {
int ans = nums[0], previous = nums[0];
for(int i = 1; i < nums.length; i++){
previous = Math.max(previous+nums[i], nums[i]);
ans = Math.max(previous, ans);
}
return ans;
}
2.Python,判断加上一个数更大还是更小
unc maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] + nums[i - 1] > nums[i] {
nums[i] += nums[i - 1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}
3.C++版本
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
// dp[i] 表示:以 nums[i] 结尾的连续子数组的最大和
vector<int> dp(len);
int ret;
dp[0] = nums[0];
ret = dp[0];
for (int i = 1; i < len; i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
if (dp[i] > ret) ret = dp[i];
}
return ret;
}
};
4.动态规划java
public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
// dp[i] 表示:以 nums[i] 结尾的连续子数组的最大和
int[] dp = new int[len];
dp[0] = nums[0];
for (int i = 1; i < len; i++) {
if (dp[i - 1] > 0) {
dp[i] = dp[i - 1] + nums[i];
} else {
dp[i] = nums[i];
}
}
// 也可以在上面遍历的同时求出 res 的最大值,这里我们为了语义清晰分开写,大家可以自行选择
int res = dp[0];
for (int i = 1; i < len; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
}
5.动态规划优化java
public class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int res = nums[0];
for (int num : nums) {
pre = Math.max(pre + num, num);
res = Math.max(res, pre);
}
return res;
}
}
6.分治java
public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private int maxCrossingSum(int[] nums, int left, int mid, int right) {
// 一定会包含 nums[mid] 这个元素
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// 左半边包含 nums[mid] 元素,最多可以到什么地方
// 走到最边界,看看最值是什么
// 计算以 mid 结尾的最大的子数组的和
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// 右半边不包含 nums[mid] 元素,最多可以到什么地方
// 计算以 mid+1 开始的最大的子数组的和
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
private int maxSubArraySum(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
return max3(maxSubArraySum(nums, left, mid),
maxSubArraySum(nums, mid + 1, right),
maxCrossingSum(nums, left, mid, right));
}
private int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}
}
7.暴力法C++
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
int max = INT_MIN;
int numsSize = int(nums.size());
for (int i = 0; i < numsSize; i++)
{
int sum = 0;
for (int j = i; j < numsSize; j++)
{
sum += nums[j];
if (sum > max)
{
max = sum;
}
}
}
return max;
}
};
8.分治C++
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
result = maxSubArrayHelper(nums, 0, numsSize - 1);
return result;
}
int maxSubArrayHelper(vector<int> &nums, int left, int right)
{
if (left == right)
{
return nums[left];
}
int mid = (left + right) / 2;
int leftSum = maxSubArrayHelper(nums, left, mid);
//注意这里应是mid + 1,否则left + 1 = right时,会无线循环
int rightSum = maxSubArrayHelper(nums, mid + 1, right);
int midSum = findMaxCrossingSubarray(nums, left, mid, right);
int result = max(leftSum, rightSum);
result = max(result, midSum);
return result;
}
int findMaxCrossingSubarray(vector<int> &nums, int left, int mid, int right)
{
int leftSum = INT_MIN;
int sum = 0;
for (int i = mid; i >= left; i--)
{
sum += nums[i];
leftSum = max(leftSum, sum);
}
int rightSum = INT_MIN;
sum = 0;
//注意这里i = mid + 1,避免重复用到nums[i]
for (int i = mid + 1; i <= right; i++)
{
sum += nums[i];
rightSum = max(rightSum, sum);
}
return (leftSum + rightSum);
}
};
四、总结
1.动态规划
时间复杂度:O(N) ,这里 N 是输入数组的长度。
2.分治
时间复杂度:O(NlogN),这里递归的深度是对数级别的,每一层需要遍历一遍数组(或者数组的一半、四分之一);
空间复杂度:O(logN),需要常数个变量用于选取最大值,需要使用的空间取决于递归栈的深度。
3.暴力法