# 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 的做法

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

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

```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]) {
}
}
//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]);
}```

Share

# Maximal Square

#### 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的边长

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

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]);
}```