Daily Archives: July 18, 2015

Best Time to Buy and Sell Stock III

Posted on by
Reply

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

这次的不同点在与要做两次交易，所以我们要找一个分界点，分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次：

第一次是从左到右扫[0-i]区间，也就是先确定buyDay，然后根据每个prices[i]来确定sellDay。

第二次是从右到左扫[i-end]区间，也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。

所以这两个循环时间都是O(n)

最后我们要用一个循环来设分界点，然后取

max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])

注意这个max不是最终答案，假设只有两天[1,2] 这种情况算下来是0，因为分界点两边都是1天不足以完成交易，而且有可能的情况是第一天买入，最后一天买进，这种情况按两次交易算也无法取到最大值，所以最后结果还要考虑到只做一次交易的情况，因为没有规定必须做两次交易

Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);

这一部分的时间复杂度也是O(n)

所以整体的时间复杂度就是O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int length = prices.length;
    int[] maxProfitEndedAt = new int[length];
    int[] maxProfitStartedFrom = new int[length];

    //get the max profit from 0 to i with one transaction
    maxProfitEndedAt[0] = 0;
    int buyDay = 0;
    for (int i = 1; i < length; i++) {
        maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
        if (prices[i] < prices[buyDay]) {
            buyDay = i;
        }
    }
    //get the max profit form i to length-1 with one transaction
    maxProfitStartedFrom[length - 1] = 0;
    int sellDay = length - 1;
    for (int i = length - 2; i >= 0; i--) {
        maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
        if (prices[i] > prices[sellDay]) {
            sellDay = i;
        }
    }
    //to have two transactions
    //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
    int maxWithTwoTransaction = 0;
    for (int i = 0; i < length - 2; i++) {
        maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
                                         maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
    }
    return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}

 

FacebookTwitterGoogle+Share

Maximal Square

Posted on by
Reply

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

Example

For example, given the following matrix:

<code>1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
</code>

Return 4.

Solution: DP side[i][j] 表示以(i,j)这个点为右下角可以组成的最大square的边长

由下图可知，大正方形由三个小正方形和(i,j)这个点这个点决定

maximum square草图

side[i][j] = min(side[i-1][j-1], side[i][j-1], side[i-1][j]) +1 //when matrix[i][j]==1

= 0 //when matrix[i][j] = 0

public int maxSquare(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    //side[i][j] = the length of the max square which (i,j) is the at right bottom corner.
    int[][] side = new int[matrix.length][matrix[0].length];
    int max = 0;
    for (int i = 0; i < matrix.length; i++) {
        side[i][0] = matrix[i][0];
        max = Math.max(max, side[i][0]);
    }
    for (int j = 0; j < matrix[0].length; j++) {
        side[0][j] = matrix[0][j];
        max = Math.max(max, side[0][j]);
    }

    for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            if (matrix[i][j] == 0) {
                side[i][j] = 0;
            } else {
                side[i][j] = Math.min(side[i - 1][j], Math.min(side[i][j - 1], side[i - 1][j - 1])) + 1;
                max = Math.max(max, side[i][j]);
            }
        }
    }
    return max * max;
}

House Robber

Posted on by
Reply

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example

Given [3, 8, 4], return 8.

Challenge

O(n) time and O(1) memory.

Solution: max[i]表示从0-i个房子里，要抢房子i的最大值

max[i] = Math.max(max[i – 2] + A[i], max[i – 1]);

public long houseRobber(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    if (A.length == 1) {
        return A[0];
    }
    if (A.length == 2) {
        return Math.max(A[0], A[1]);
    }

    //max[i] = for [0-i], the max value if rob house i
    long[] max = new long[A.length];
    max[0] = A[0];
    max[1] = A[1];
    for (int i = 2; i < A.length; i++) {
        max[i] = Math.max(max[i - 2] + A[i], max[i - 1]);
    }
    return Math.max(max[A.length - 1], max[A.length - 2]);
}