当前位置：首页 > article >正文

动态规划之子数组算法专题

article 2024/11/16 13:02:40

一, 最大子数组和

状态表示
dp[i] 表示以i位置结尾的最大的子数组和
状态转移方程
分成两种情况:
1.i位置本身就是最大的数组
dp[i] = nums[i]
2.以i位置结尾的最大的子数组和为 i - 1位置结尾的最大的子数组和 + nnums[i]
dp[i] = dp[i - 1] + nums[i]

dp[i] = max(dp[i - 1] + nums[i], nums[i])

初始化
dp[0] = nums[0]
填表顺序
从左往右
返回值
返回所有数的最大值

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ret = dp[0];
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}

二. 环形子数组的最大和

先将环形的问题转换成简单的问题:
如果不存在环形, 和上一题是类似的
存在环形, 我们要找收尾相接的最大值, 相当于是找中间的最小值, 最后再用sum - 最小值就是最大值

状态表示
f[i] 表示以i位置结尾的最大的子数组和
g[i] 表示以i位置结尾的最小的子数组和
状态转移方程
分成两种情况:
1.i位置本身就是最大/小的数组
f[i] = nums[i] g[i] = nums[i]
2.以i位置结尾的最大的子数组和为 i - 1位置结尾的最大/小的子数组和 + nnums[i]
f[i] = f[i - 1] + nums[i] g[i] = g[i - 1] + nums[i]

f[i] = max(f[i - 1] + nums[i], nums[i])
g[i] = min(g[i - 1] + nums[i], nums[i])

初始化
f[0] = nums[0] g[0] = nums[0]
填表顺序
从左往右
返回值
返回f表最大值和sum - g表最小值的最大值
细节: 如果sum 和g表最小值相等时, 结果是不正确的, 返回f表最大值即可
环形子数组的最大和

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = nums[0];
        g[0] = nums[0];
        int max = f[0];
        int min = g[0];
        int sum = nums[0];
        for(int i = 1; i < n;i++){
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            max = Math.max(max, f[i]);
            g[i] = Math.min(g[i - 1] + nums[i], nums[i]);
            min = Math.min(min, g[i]);
            sum += nums[i];
        }
        System.out.println(max);
        System.out.println(min);
        System.out.println(sum);

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

    }
}

三. 乘积最大子数组

乘积最大子数组

状态表示
dp[i] 表示以i位置结尾的最大的子数组的成绩
状态转移方程
分成两种情况:
1.i位置本身就是最大的数组
dp[i] = nums[i]
2.以i位置结尾的最大的子数组和为 i - 1位置结尾的最大的子数组的乘积 * nums[i]
但是此时就会出现一个问题, 如果nums[i]为负数, 那么乘上前面的最大值, 会成为一个更小的负数, 并不是我们想要的, 所以当nums[i]为负数时, 我们要乘的是前面的最小值
最大值 f[i] = f[i - 1] * nums[i] 或者 f[i] = g[i - 1] * nums[i]
最小值 g[i] = g[i - 1] * nums[i] 或者 g[i] = f[i - 1] * nums[i]

f[i] = max(f[i - 1] * nums[i], nums[i], g[i - 1] * nums[i])
g[i] = min(g[i - 1] * nums[i], nums[i], f[i - 1] * nums[i])

初始化
可以使用增加虚拟节点的方式, f[0] = 1 g[0] = 1即可, 不会影响结果
填表顺序
从左往右
返回值
返回f表的最大值

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        f[0] = 1;
        g[0] = 1;
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            f[i] = Math.max(Math.max(f[i - 1] * nums[i - 1], nums[i - 1]), g[i - 1] * nums[i - 1]);//注意下标映射
            g[i] = Math.min(Math.min(g[i - 1] * nums[i - 1], nums[i - 1]), f[i - 1] * nums[i - 1]);
            ret = Math.max(ret, f[i]);
        }

        return ret;
    }
}

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

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

状态表示
f[i] 表示以i位置结尾的乘积为正数的子数组的最长长度
g[i] 表示以i位置结尾的乘积为负数的子数组的最长长度
状态转移方程
分成两种情况:
1.nums[i]为正数, 那么就需要找前面为正数的最长数组长度f[i - 1]
f[i] = f[i - 1] + 1
2.nums[i]为负数, 那么就需要找前面为负数的最长数组长度g[i - 1]
但是如果g[i - 1] == 0, 那么说明前面的数乘积不是负数, 此时长度应该为0
f[i] = g[i - 1] == 0?0 : g[i - 1] + 1

g[i]与f[i]类似:
1.nums[i]为负数, 那么就需要找前面为正数的最长数组长度f[i - 1]
g[i] = f[i - 1] + 1
2.nums[i]为正数, 那么就需要找前面为负数的最长数组长度g[i - 1]
但是如果g[i - 1] == 0, 那么说明前面的数乘积不是负数, 此时长度应该为0
g[i] = g[i - 1] == 0?0 : g[i - 1] + 1

nums[i] > 0, f[i] = f[i - 1] + 1 g[i] = g[i - 1] == 0?0 : g[i - 1] + 1
nums[i] < 0, f[i] = g[i - 1] == 0?0 : g[i - 1] + 1 g[i] = f[i - 1] + 1

初始化
可以使用增加虚拟节点的方式, f[0] =0 g[0] = 0即可, 不会影响结果
填表顺序
从左往右
返回值
返回f表的最大值

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; 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(f[i], ret);
        }

        return ret;
    }
}

五. 等差数列划分

等差数列划分

状态表示
dp[i] 表示以i位置结尾的所有的子数组中等差数列的个数
状态转移方程
等差数列最少需要三个数构成
分成两种情况:
1.nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]
说明此时这个三个数能构成等差数列, 那么前面的所有等差数列加上i位置, 还是等差数列, 所以
dp[i] = dp[i - 1] + 1
2.nums[i] - nums[i - 1] != nums[i - 1] - nums[i - 2]
说明此时这个三个数不能构成等差数列, 那么以i位置结尾的所有的子数组中等差数列的个数为0
dp[i] = 0

dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;

初始化
dp[0] = 0 dp[1] = 0
填表顺序
从左往右
返回值
返回所有等差数列个数即sum

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int sum = 0;
        for(int i = 2; i < n; i++){
            dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            sum += dp[i];
        }
        return sum;
    }
}

六. 最长湍流子数组

最长湍流子数组

状态表示
f[i] 表示以i位置结尾, 最后呈现"上升"状态下的最大湍流子数组的长度
g[i] 表示以i位置结尾, 最后呈现"下降"状态下的最大湍流子数组的长度
状态转移方程
分成两种情况:
1.呈上升趋势
f[i] = g[i - 1] + 1
g[i] = 1(无法呈上升趋势, 所以只能作为开头)
2.呈下降趋势
g[i] = f[i - 1] + 1
f[i] = 1
3.如果和前一个相等
g[i] = 1
f[i] = 1
初始化
可以全部初始化为1, 可以少考虑很多情况
填表顺序
从左往右
返回值
返回f表和g表的最大值

class Solution {
    public int maxTurbulenceSize(int[] nums) {
        int n = nums.length;
        
        int[] f = new int[n];
        int[] g = new int[n];

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

七. 单词拆分

单词拆分

状态表示
dp[i] 表示[0, i]区间内的字符串, 能否被字典中的单词拼接而成, 返回true, false
状态转移方程
用j来标记(j, i)区间内的单词, dp[i] 只需判断(j, i)区间内的单词在字段中是否存在, 并且[0, j - 1]区间内的字符串, 能否被字典中的单词拼接而成, 即dp[j - 1]

dp[i] 为true: dp[i - 1]为true && (j, i)区间内的单词在字段中存在

初始化
添加一个辅助节点, 但是因为操作字符, 我们可以在字符前添加一个元素占位, 这样就不用考虑后续下标映射的问题
填表顺序
从左往右
返回值
返回最后一个位置dp[n]时候为true

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //优化, 将字典里面的单词存到哈希表中
        Set<String> hash = new HashSet(wordDict);

        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        s = " " + s;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                if(dp[j - 1] && hash.contains(s.substring(j, i + 1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

八. 环绕字符串中唯一的子字符串

环绕字符串中唯一的子字符串

状态表示
dp[i] 表示以i位置为结尾的所有子串中在base中出现的个数
状态转移方程
1.长度为1, 那么字符本身一定在base中
2.长度 > 1, 如果i位置和i - 1位置拼接后在base中, 即s[i - 1] + 1 = s[i] || s[i - 1] = ‘z’ && s[i] = ‘a’, 那么dp[i] = 以i - 1位置为结尾的所有子串中在base中出现的个数, 即dp[i - 1]

dp[i] = dp[i - 1] + 1

初始化
可以先全部初始化为1, 就不用考虑长度为1的情况
填表顺序
从左往右
返回值
因为可能有重复的情况, 所以要去重
以某一个字符位置为结尾的所有子串中在base中出现的个数, 如果有多个, 那么一定取最大的那个, 因为小的在大的中一定包含了
所以返回所有字符取完最大后的和

class Solution {
    public int findSubstringInWraproundString(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < n; i++){
            if(ss[i - 1] + 1 == ss[i] ||( ss[i - 1] == 'z' && ss[i] == 'a')){
                dp[i] += dp[i - 1];
            }
        }
        int[] ret = new int[26];
        for(int i = 0; i < n; i++){
            ret[ss[i] - 'a'] = Math.max(ret[ss[i] - 'a'], dp[i]);
        }
        int sum = 0;
        for(int i = 0; i < 26; i++){
            sum += ret[i];
        }
        return sum;
    }
}