少女祈祷中...

题目

给定一个整数数组nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例1

  • 输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
  • 输出:6
  • 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例2

  • 输入:nums = [1]
  • 输出:1

示例3
输入:nums = [5,4,-1,7,8]
输出:23

《代码随想录》算法公开课
力扣题目链接

思路

暴力解法

  • 暴力解法的思路,第一层for就是设置起始位置,第二层 for循环遍历数组寻找最大值
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
public int maxSubArray(int[] nums){
//先将结果设为最小整数,以便于后续结果做对比不被影响
int res = Integer.MIN_VALUE;
//单个子序列的总和
int count = 0;
for(int i = 0; i < nums.length; i++){
//每次进行新一轮遍历时,都重置子序列和
count = 0;
for(int j = i; j < nums,length; j++){
//固定外层nums[i]移动j指针,寻找最大子序列和
count += nums[j];
//当前子序列和大于res时,将其count值赋给res
res = count > res ? count : res;
}
}
return res;
}
}

注:此方法的时间复杂度为O(n^2),空间复杂度为O(1),一般会超过题目给定的时间限制,提示超时错误

贪心算法

所谓贪心算法,就是在子序和为负数时,直接舍弃当前count,对其count进行重新赋值0的操作,因为负数只会拉低综合,这便是局部最优。

从代码角度上来讲:遍历nums,从头开始用count累积,如果count一旦加上nums[i]变为负数,那么就应该从nums[i+1]开始从0累积count了,因为已经变为负数的count,只会拖累总和。

  • 注:这相当于是暴力解法中的不断调整最大子序和区间的起始位置。

代码实现

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int maxSubArray(int[] nums) {
//当长度为1时直接返回其值便是最大子序和
if (nums.length == 1){
return nums[0];
}
//将返回值初始为整型最小值,以便后续赋值
int max = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++){
count += nums[i];
//先对比取出最大值,再判断count是否<0,这么做是为了防止最大值便是负数导致遗漏
max = Math.max(max, count);
// 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
if (count <= 0){
count = 0;
}
}
return max;
}
}
Powered By Valine
v1.5.1