问题说明
给你一个整数数组 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
提示:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。
Related Topics
解决方案
package leetcode.editor.cn;
/**
* 最大子数组和
* @date 2022-02-12 11:18:44
* @author 沙漠渔
*/
public class 最大子数组和{
static
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int maxSubArray(int[] nums) {
int max = 0, lastMaxSum = 0;
for(int i = 0; i < nums.length; i++){
if(i == 0) {
lastMaxSum = nums[i];
max = lastMaxSum;
}else{
lastMaxSum = Math.max(nums[i],nums[i] + lastMaxSum);
max = Math.max(lastMaxSum, max);
}
}
return max;
}
}
//leetcode submit region end(Prohibit modification and deletion)
static class ListNode {
int val;
ListNode next;
public ListNode(int val) { this.val = val; }
public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
/**
* 最终测试主方法
*/
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxSubArray(new int[]{
-2,1,-3,4,-1,2,1,-5,4
}));
}
}
评论区