- 题目
- 思路
- 代码
给你一个整数数组 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
定义一个临时变量temp用来储存临时和,result用来储存总的最大和。遍历数组,每遍历一个元素,将他和前面的已遍历的元素的和(temp)相加:
(1)如果当前元素 + 前面已遍历的元素的和(temp)>= 该元素,说明前面已遍历的元素的和(temp) >= 0,相加的话可以使这个值继续增大。所以更新temp的值,使 temp = temp + 该元素;
(2)如果当前元素 + 前面已遍历的元素的和(temp)< 该元素,说明前面已遍历的元素的和(temp)< 0,如果当前元素 + temp 不仅不会变大,还会变小,不符合题目所要求的 最大和,此时最大的值就是当前元素,所以更新temp的值为当前元素。
最后将result和temp相比较,如果temp > result,就交换它俩的值。
代码public class Solution {
public static int maxSubArray(int[] nums) {
int result = nums[0];
int temp = nums[0];
for(int i = 1;i < nums.length;i++){
if(temp + nums[i] >= nums[i] ){
temp = temp + nums[i];//更新temp的值,使 temp = temp + 该元素
}else{
temp = nums[i];//更新temp的值为当前元素
}
if(temp > result){
result = temp;
}
}
return result;
}
}
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)