首页 > 其他 > 详细

53.最大子序和

时间:2020-05-04 18:52:11      阅读:51      评论:0      收藏:0      [点我收藏+]

技术分享图片
技术分享图片

解法1

思路

  • 数组中的每个元素 依次 作为子序的头元素 ,枚举各自构成子序的结果
  • 双for O(n^2)
  • 160 ms

代码

/**
     * 双for O(n^2) 160ms
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int ans=nums[0],len=nums.length;
        for(int i=0;i<len;i++){
            int sum=nums[i];
            ans=Math.max(ans, sum);
            for(int j=i+1;j<len;j++){
                sum+=nums[j];
                ans=Math.max(ans, sum);
            }
        }
        return  ans;
    }

优解 (动态规划)

思路

作者:lizhiqiang-3

技术分享图片

技术分享图片
技术分享图片
技术分享图片

代码

/**
     * 动态规划
     * 1ms   O(n)
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums){
        int len=nums.length;
        if(len==0) return 0;
        int[] dps=new int[len];
        dps[0]=nums[0];
        for(int i=1;i<len;i++){
            if(dps[i-1]>=0){
                dps[i]=dps[i-1]+nums[i];
            }else{
                dps[i]=nums[i];
            }
        }

        int ans=dps[0];
        for(int dp:dps){
            ans=Math.max(ans, dp);
        }
        return ans;
    }

优化

/**
     * 优化
     * @param nums
     * @return
     */
    public int maxSubArray3(int[] nums){
        int len=nums.length;
        if(len==0) return 0;
        int max=nums[0];
        int subMax=nums[0];
        for(int i=1;i<len;i++){
            if(subMax>=0){
                subMax=subMax+nums[i];
            }else{
                subMax=nums[i];
            }
            max=Math.max(max, subMax);
        }
        return max;
    }

动态规划

动态规划算法思想

53.最大子序和

原文:https://www.cnblogs.com/yh-simon/p/12827631.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!