LeetCode（121&53） 买卖股票的最佳时机&最大子序和

121. 买卖股票的最佳时机

本题来自LeetCode：121. 买卖股票的最佳时机

题目详情

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目分析

题目要求`买入价格 卖出价格`，否则最大利润为`0`；

其实题意就是，从一个数组中，找一个包括两个数值的子序列`price1、price2`， 求`profit = price2 - price1`的最大值，`profit`需要满足`profit 0`；

题目解答

暴力法

暴力法的思想：从价格数组中，选定一个买入价 b，再从后面的价格中选定一个卖出价 s，迭代即可。

// 时间复杂度`O(n ^ 2)`，空间复杂度`O(1)`
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length  2) {
            return 0;
        }
        // 初始最大利润
        int maxProfit = 0;
        for (int i = 0; i  prices.length - 1; i++) {
            // 买入价
            int b = prices[i];
            for (int j = i + 1; j  prices.length; j++) {
                // 卖出价
                int s = prices[j];
                if (s  b) {
                    maxProfit = Math.max(s - b, maxProfit);
                }
            }
        }
        return maxProfit;
    }
}

动态规划

动态规划的思想：记录当前 最低买入价和 最大利润，和之后的 卖出价依次比较

若`卖出价`低于`最低买入价`，则将更新`最低买入价`等于`卖出价`;

若`卖出价`高于`最低买入价`，则比较`最大利润`与`卖出价 - 最低买入价`的大小；

// 时间复杂度`O(n)`，空间复杂度`O(1)`
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length  2) {
            return 0;
        }
        // 初始最大利润
        int maxProfit = 0;
        // 最低买入价
        int minBuyPrice = prices[0];
        for (int i = 1; i  prices.length; i++) {
            minBuyPrice = Math.min(minBuyPrice, prices[i]);
            maxProfit = Math.max(prices[i] - minBuyPrice, maxProfit);
        }
        return maxProfit;
    }
}

53. 最大子序和

本题来自LeetCode：53. 最大子序和

题目详情

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

1. 动态规划

题目分析

该题和上面的题类似，也可以采用动态规划来解答：

定义`dp[i]`为当前与`i`连续的子数组的最大和，即`...、i-1, i`子序列；

若`dp[i - 1] 0`，那么`dp[i] = dp[i] + nums[i]`；

若`dp[i - 1] 0`，那么`dp[i] = nums[i]`；

同时定义`maxSum`为全局的最大和；

代码实现

// 时间复杂度`O(n)`，空间复杂度`O(n)`
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            throw new RuntimeException();
        }
        int[] dp = new int[nums.length];
        int maxSum = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i  nums.length; i ++) {
            if(dp[i - 1]  0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

注意到以上实现的 dp[]数组，每一次迭代只用到值 dp[i - 1]，因此用一个变量暂存 dp[i - 1]即可；
优化后的解答如下：

// 时间复杂度`O(n)`，空间复杂度`O(1)`
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            throw new RuntimeException();
        }
        int maxSum = nums[0];
        int currentSum = nums[0];
        for(int i = 1; i  nums.length; i ++) {
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

2. 分治法

题目分析

分治法，必然需要将数组分成`nums[0...i]`、`nums[i+1...n]`两个数组；

最大和可能是以下三个子序列里的最大值 a. 左半数组的最大子序列和； b. 右半数组的最大子序列和； c. 跨越中间值的最大子序列和；

其中 2.a， 2.b的值可通过递归获得， 2.c可通过简单计算获得；

该实现参考了 geeksforgeeks的文章 Maximum Subarray Sum using Divide and Conquer algorithm；

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            throw new RuntimeException();
        }
        return findMaxSubArraySum(nums, 0, nums.length - 1);
    }

    public int findMaxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right)  1;

        // a. 左半数组的最大子序列和
        int leftMaxSum = findMaxSubArraySum(nums, left, mid);
        // b. 右半数组的最大子序列和
        int rightMaxSum = findMaxSubArraySum(nums, mid + 1, right);
        // c. 跨越中间值的最大子序列和
        int crossMaxSum = findCrossMidMaxArraySum(nums, left, mid, right);

        return Math.max(Math.max(leftMaxSum, rightMaxSum), crossMaxSum);
    }

    public int findCrossMidMaxArraySum(int[] nums, int left, int m, int right) {
        // m一定是合法的下标

        int tempSum = 0;
        // 记录左边和m连续的最大和（包含nums[m]）
        int leftSum = Integer.MIN_VALUE;
        for(int i = m; i = left; i--) {
            tempSum += nums[i];
            leftSum = Math.max(tempSum, leftSum);
        }

        tempSum = 0;
        // 记录右边和m连续的最大和
        int rightSum = Integer.MIN_VALUE;
        for(int i = m + 1; i = right; i++) {
            tempSum += nums[i];
            rightSum = Math.max(tempSum, rightSum);
        }
        return leftSum + rightSum;
    }
}

原文始发于微信公众号（xiaogan的技术博客）：