侧边栏壁纸
博主头像
沙漠渔

把過去的累積,善用到當下

  • 累计撰写 490 篇文章
  • 累计创建 295 个标签
  • 累计收到 960 条评论
标签搜索

目 录CONTENT

文章目录

[leetcode]最大子数组和题解

沙漠渔
2022-05-14 / 0 评论 / 0 点赞 / 87 阅读 / 1,539 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题说明

给你一个整数数组 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
            }));
        }
    }
    
    0
    广告 广告

    评论区