一起学习交流~

最大子数组和-dp最优子结构入门

算法 laomuji 8个月前 (01-16) 314次浏览 已收录 0个评论

前言

题目来自力扣,我刷了后觉得这个是很经典的dp入门题,所以写一下

题目要求

题目

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。

输入输出

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
输入:nums = [5,4,-1,7,8]
输出:23

解析

比如有如下数据,每个位置的最优解为

-2 1 -3 4 -1 2 1 -5 4
-2 1 -2 4 3 5 6 1 5

可以发现
如果前面的最大值为正数
那么要加上一个的结果最大
如果前面的最大值为负数
那么不加上一个的结果最大

解法

暴力

    //暴力,超时
    int maxSubArrayA(vector<int>& nums){
        int size = nums.size();
        int maxSum = nums[0];
        for(int i = 0;i<size;i++){
            int currentNum = 0;
            for(int j =i;j<size;j++){
                currentNum +=nums[j];
                if(currentNum>maxSum){
                    maxSum = currentNum;
                }
            }
        }
        return maxSum;
    }

dp解A

    int maxSubArrayDPA(vector<int>& nums){
        //dp,记录每个位置的最大值
        vector<int>dp(nums.size());
        dp[0]=nums[0];
        int maxSum = dp[0];
        for(int i =1;i<nums.size();i++){
            if(dp[i-1]>0){
                //如果上一个为正数,要加上一个会更大
                dp[i]=nums[i]+dp[i-1];
            }else{
                //如果上一个为负数,不加上一个会更大
                dp[i]=nums[i];
            }
            if(dp[i]>maxSum)maxSum=dp[i];
        }

        return maxSum;
    }

dp解B

    int maxSubArrayB(vector<int>& nums) {
        //因为 每个位置只依赖上一个位置
        //所以可以省略掉dp数组,只用一个变量维护
        int maxSum = nums[0];
        int preNum = nums[0];
        for(int i =1;i<nums.size();i++){
            if(preNum>0){
                preNum = preNum+nums[i];
            }else{
                preNum =nums[i];
            }
            if(preNum>maxSum)maxSum =preNum;
        }
        return maxSum;
    }
喜欢 (1)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论