题目
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
示例
示例1：
java
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例2：
java
输入：nums = [1]
输出：1
示例3：
java
输入：nums = [5,4,-1,7,8]
输出：23
实现
方法一：贪心算法
思路：
- 若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列。
也就是说，指针指向当前数时，前面的数列如果和小于0，前面的数列就不要了，因为小于0 ，即使加下去也会变得更小，就重新从当前指针开始算最大的数列。
java
public static int maxSubArray(int[] nums) {
int sum=0;
int maxNum =0;
for (int num:nums){
if (sum>0){
sum+=num;
}else {
sum=num;
}
maxNum=Math.max(sum,maxNum);
}
return maxNum;
}
复杂度分析：
- 时间复杂度：O(N)，只遍历一次数组。
- 空间复杂度：O(1)，只是用了常数空间。
方法二：动态规划
思路：
- 若前一个元素大于0，则将其加到当前元素上。
也就是说，如果前面的数时大于0的，那加上后面一个数，肯定是大于后面一个数的，好比5和-2，5+(-2)肯定是大于-2的。
如果前面的数是小于0的，那加起来肯定是小于后一位数的。
java
public static int maxSubArray(int[] nums) {
for (int i=1;i<nums.length;i++){
if (nums[i-1]>0)
nums[i]+=nums[i-1];
}
Arrays.sort(nums);
return nums[nums.length-1];
}
复杂度分析：
时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。
本文是原创文章，采用 CC BY-NC-SA 4.0 协议，完整转载请注明来自 小码同学
评论
隐私政策
0/500
滚动到此处加载评论...