最大子序和
题目形容:给定一个整数数组 nums,找到一个具备最大和的间断子数组(子数组起码蕴含一个元素),返回其最大和。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:动静布局
首先,初始化 max 和sum都为 nums 的第一个元素的值,而后从第 2 位开始遍历数组:
- 当
sum <= 0
时,sum设置为以后索引为的值,也就是摈弃之前累加的值;- 当
sum > 0
时,sum加上以后索引位的值,累加;- 而后每次便当时 max 取max和 sum 的较大者。
最初,返回 max 即为最初后果。
public class LeetCode_053 {public static int maxSubArray(int[] nums) {int max = nums[0], sum = nums[0];
for (int i = 1; i < nums.length; i++) {if (sum <= 0) {sum = nums[i];
} else {sum = sum + nums[i];
}
max = Math.max(max, sum);
}
return max;
}
public static void main(String[] args) {int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(nums));
}
}
【每日寄语】在繁忙的日子里,要学会每天给本人找一个开心的理由,哪怕只是,阳光很暖,电量很满。