【动态规划】子数组、子串系列I|最大子数组和|环形子数组的最大和|乘积最大子数组|乘积为正数的最长子数组长度

一、最大子数组和

最大子数组和

算法原理: 

 ????细节:

1.返回值为dp表每个位置的最大值,而不是只看最后一个位置,因为可能最后一个位置都不选 

2.可以直接在填dp表的时候就进行返回值的比较

3.如果初始化选择多开一个位置,那么就需要注意下标的映射

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n+1];//dp表示以i位置为结尾的所有子数组中的最大和

        int ret = Integer.MIN_VALUE;
        for(int i=1;i<n+1;i++) {
            dp[i] = Math.max(nums[i-1],dp[i-1]+nums[i-1]);//注意下标映射
            ret = Math.max(ret,dp[i]);
        }
        
        return ret;
    }
}

二、环形子数组的最大和

918. 环形子数组的最大和

算法原理

 ????细节: 

1.因为是环形的,我们就跟上次打家劫舍II一样的思路,进行拆分分类讨论,分为(1)结果就在数组中间,跟上题一样,(2)结果在两边,这个时候求最大,那么反向思考,就考虑中间区间最小,进一步转化为(1)

2.返回值:注意当nums数组中元素全为负数时,那么sum-gmin为0,而根据题意,此时的返回值只能为负数,那么就需要特殊考虑这种情况

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;

        int[] f = new int[n+1];//结果在中间:求以i位置为结果的所有子数组的最大值
        int[] g = new int[n+1];//结果在两边:求以i位置为结果的所有子数组的最小值

        int fmax = Integer.MIN_VALUE;
        int gmin = Integer.MAX_VALUE;
        int sum = 0;
        for(int i=1;i<n+1;i++) {
            int x = nums[i-1];
            sum += x;
            f[i] = Math.max(x,f[i-1]+x);
            fmax = Math.max(fmax,f[i]);
            g[i] = Math.min(x,g[i-1]+x);
            gmin = Math.min(gmin,g[i]);
        }

        return sum==gmin?fmax:Math.max(fmax,sum-gmin);

    }
}

三、乘积最大子数组

152. 乘积最大子数组

算法原理

????细节: 

1.如果只用一个f表时,在分类讨论的时候会发现当nums[i]为负数的时候,f[i-1]*nums[i]也为负,那么就不可能是最大乘积,所以还需要一个g表来表示最小乘积,同时填g表的时候跟f表一样的考虑(考虑nums[i]是正负+长度为1三种情况

2.初始化的时候注意是乘法,f[0]和g[0]都应该初始化为1

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;

        int[] f = new int[n+1];//以i位置为结果的所有子数组的最大乘积
        int[] g = new int[n+1];//以i位置为结果的所有子数组的最小乘积

        f[0] = g[0] = 1;

        int ret = Integer.MIN_VALUE;
        for(int i=1;i<n+1;i++) {
            int x = nums[i-1],y = f[i-1]*nums[i-1],z = g[i-1]*nums[i-1] ;
            f[i] = Math.max(x,Math.max(y,z));
            g[i] = Math.min(x,Math.min(y,z));
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}

四、乘积为正数的最长子数组长度

1567. 乘积为正数的最长子数组长度

算法原理

????细节: 

1.本题跟上题一样,一个f表无法解决问题,需要一个g表来辅助

2.(1)在分析f表的状态方程时,长度大于1且nums[i]<0的情况下:要判断g[i-1](即最长的负数乘积长度)是否存在的情况,不存在就为0,存在才是g[i-1]+1;在分析g表的状态方程时,长度大于1且nums[i]>0的情况同理

(2)分析完f表和g表可以进行合并,直接分为nums[i]大于0和小于0的情况即可

3.初始化:根据上面的状态表示f[0]和g[0]全部初始化为0即可

class Solution {
    public int getMaxLen(int[] nums) {
        int n = nums.length;

        int[] f = new int[n+1];
        int[] g = new int[n+1];

        int ret = Integer.MIN_VALUE;
        for(int i=1;i<n+1;i++) {
            if(nums[i-1]>0) {
                f[i] = f[i-1] + 1;
                g[i] = g[i-1]==0?0:g[i-1]+1;
            }
            else if(nums[i-1]<0) {
                f[i] = g[i-1]==0?0:g[i-1]+1;
                g[i] =  f[i-1] + 1;
            }
            ret = Math.max(ret,f[i]);
        }
        return ret;
    }
}

上一篇:对于Docker和Podman的一点使用经验


下一篇:正点原子Linux学习笔记(五)FrameBuffer 应用编程