Leetcode剑指Offer刷题 - 第九天

Leetcode剑指Offer刷题指南：

Leetcode剑指Offer刷题-学习计划目录_DEGv587的博客-CSDN博客

剑指 Offer 42. 连续子数组的最大和 

解法：动归

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            //两种情况：dp[i - 1] > 0  max = dp[i - 1] + nums[i]
            //         dp[i - 1] <=0  max = nums[i]
            //所以 max 肯定取自于(nums[i] + dp[i - 1], nums[i])
            dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

剑指 Offer 47. 礼物的最大价值

解法：动归

1.初始化：

第一个元素 ret[0][0] = grid[0][0]第一行 i == 0 && j >= 1 --> grid[i][j] += grid[i][j - 1];第一列 j == 0 && i >= 1 --> grid[i][j] += grid[i - 1][j];

2.状态递推：i != 0 && j != 0 --> grid[i][j] += Math.grid(ret[i][j - 1], grid[i - 1][j])

3.返回结果：grid[m - 1][n - 1]

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        //初始化第一行
        for (int j = 1; j < n; ++j) {
            grid[0][j] += grid[0][j - 1];
        }
        //初始化第一列
        for (int i = 1; i < m; ++i) {
            grid[i][0] += grid[i - 1][0];
        }
        //中间元素
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }
}

优化版：

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (i == 0) {
                    grid[i][j] += grid[0][j - 1];
                } else if (j == 0) {
                    grid[i][j] += grid[i - 1][0];
                } else {
                    grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }

        return grid[m - 1][n - 1];
    }
}