1/23，subarray & stock (DP)
类型：prefix sum array,
template for prefix sum.
public int minSubarray(int[] nums) {
int globalMin = Integer.MAX_VALUE; // not really..
int localMax = 0; // ends with current character && contiguous
int prefixSum = 0;
for (int num : nums) {
prefixSum += num;
globalMin = Math.min(globalMin, prefixSum - localMax);
localMax = Math.max(localMax, prefixSum);
}
return globalMin;
}
Maximum Subarray
题中给一个array，然后要求contiguous subarray的largest sum，
用区间和的思路：
the basic idea is to find the largest difference between the sums when you summing up the array from left to right. The largest difference corresponds to the sub-array with largest sum
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] preSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
int max = Integer.MIN_VALUE, min = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, preSum[i] - min);
min = Math.min(min, preSum[i]);
}
return max;
}
}
用Kadane's Algorithm: reference
It's a DP problem. The basic idea is that we won't add a negative cumulative sum. I would rather start a new subarray at this point. The state equation is as follows: f[i] = f[i-1] > 0 ? nums[i] + f[i-1] : nums[i]; but the space would be O(n),
It feels more like a Greedy algorithm to me. 求max subarray可以看成下题求stock的max profit，可以用一个for循环的greedy算法。所谓的greedy就是考虑使用哪些变量，使每次循环都产生local solution，并且keep track of这些变量。这样在循环结束时，就能得到global solution。
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// Kadane's algorithm
int maxSoFar = nums[0], maxEnding = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEnding = Math.max(maxEnding + nums[i], nums[i]);
maxSoFar = Math.max(maxSoFar, maxEnding);
}
return maxSoFar;
}
}
Kadane's Algorithm相比prefix sum的特点是，必须要以nums[0]做初始化，从index = 1开始搜，优点是在处理prefix product的时候更容易处理好“-5”和“0”的情况。
Also, we can use divide and conquer to solve this problem:
Using Divide and Conquer approach, we can find the maximum subarray sum in O(nLogn) time.
Following is the Divide and Conquer algorithm.
1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint
The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that
the subarray crosses the midpoint? We can easily find the crossing sum in linear time.
The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid,
then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1.
Finally, combine the two and return.
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
return maxSubArrayHelper(nums, 0, nums.length - 1);
}
private int maxSubArrayHelper(int[] nums, int left, int right) {
if (left == right) return nums[left];
int mid = left + (right - left) / 2;
int leftans = maxSubArrayHelper(nums, left, mid); // possible solution inside this array
int rightans = maxSubArrayHelper(nums, mid + 1, right);
int leftmax = nums[mid];
int rightmax = nums[mid + 1];
int temp = 0;
for (int i = mid; i >= left; i--) { // search for possible solution across two arrays
temp += nums[i];
if (temp > leftmax) leftmax = temp;
}
temp = 0;
for (int i = mid + 1; i <= right; i++) {
temp += nums[i];
if (temp > rightmax) rightmax = temp;
}
return Math.max(Math.max(leftans, rightans), leftmax + rightmax);
}
}
Minimum Subarray
Just similar to the Maximum Subarray, we can use prefix sum and DP to solve the problem.
prefix sum: Note globalMin = Integer.MAX_VALUE, localMin = 0, then update the globalMin first, then update localMin.
// prefix sum to solve the problem
public static int minSubArray(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// for each loop, we only need current prefix sum
int prefixSum = 0;
int globalMin = Integer.MAX_VALUE, localMax = 0;
// prefix - max; -> globalMin of difference
// max -> localMax of prefix sum
for (int num: nums) {
prefixSum += num;
globalMin = Math.min(globalMin, prefixSum - localMax); //
localMax = Math.max(localMax, prefixSum);
}
return globalMin;
}
DP approach: Note globalMin = localMin = nums[0], then update the localMin first, then update globalMin.
// use DP algo to solve the problem.
public static int minSubArray2(int[] nums) {
if (nums == null || nums.length == 0) return 0;
// f[i] = f[i - 1] < 0 ? f[i - 1] + nums[i] : nums[i] f[i] is the minimum sum that ends with current number...
int globalMin = nums[0], localMin = nums[0];
for (int i = 1; i < nums.length; ++i) {
localMin = Math.min(nums[i], localMin + nums[i]);
globalMin = Math.min(globalMin, localMin);
}
return globalMin;
}
Maximum Subarray II
Descriptions: Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.
How to solve?
We need to get prefix sum array and two dp[] array. Left[i] represent the max subarray sum from the most left to index i. Right[i] represents the max subarray sum from the most right to the index i.
public int maxTwoSubArrays(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) return 0;
int n = nums.size();
// maximum subarray value from left/ right with n elements
int[] left = new int[n];
int[] right = new int[n];
int prefixSum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i) {
prefixSum += nums.get(i);
max = Math.max(max, prefixSum - minSum);
minSum = Math.min(minSum, prefixSum);
left[i] = max;
}
prefixSum = 0;
minSum = 0;
max = Integer.MIN_VALUE;
for (int i = n - 1; i >= 0; --i) {
prefixSum += nums.get(i);
max = Math.max(max, prefixSum - minSum);
minSum = Math.min(minSum, prefixSum);
right[i] = max;
}
int rst = Integer.MIN_VALUE;
for (int i = 0; i < n - 1; i++) {
rst = Math.max(rst, left[i] + right[i + 1]);
}
return rst;
}
Maximum Subarray III
Descriptions: Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.
How to solve?
to do
public class Solution {
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping sub arrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
public int maxSubArray(int[] nums, int k) {
// write your code here
if(nums == null || nums.length == 0) return 0;
int n = nums.length;
int[][] localMax = new int[n + 1][k + 1];
int[][] globalMax = new int[n + 1][k + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= k && j <= i; j++){
localMax[j - 1][j] = Integer.MIN_VALUE;
localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1])
+ nums[i - 1];
if(i == j) globalMax[i][j] = localMax[i][j];
else globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]);
}
}
return globalMax[n][k];
}
}
Maximum Product Subarray
This problem is similar to the maximum subarray, can use DP to solve. But in the process, we need to maintain two variables, max and min for the previous product.
class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) return 0;
//Loop through the array, each time remember the max and min value for the previous product,
//the most important thing is to update the max and min value: we have to compare among max * A[i],
//min * A[i] as well as A[i], since this is product, a negative * negative could be positive.
int maxSoFar = nums[0], minLocal = nums[0], maxLocal = nums[0];
for (int i = 1; i < nums.length; ++i) {
int temp = maxLocal;
maxLocal = Math.max(Math.max(maxLocal * nums[i], minLocal * nums[i]), nums[i]);
minLocal = Math.min(Math.min(temp * nums[i], minLocal * nums[i]), nums[i]);
maxSoFar = Math.max(maxSoFar, maxLocal);
}
return maxSoFar;
}
}
Maximum size subarray sum equals k
The basic idea behind it is prefix sum array + two sum. Just use prefix sum array to check the sum of the range and use two sum to identify the index quickly. But bear in mind that the length is error-prone, so please be careful.
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if (nums == null || nums.length == 0) return 0;
// key: prefix sum
// value: index
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 0);
int sum = 0, size = 0;
for (int i = 0; i < nums.length; ++i) {
sum += nums[i];
if (map.containsKey(sum - k)) {
size = Math.max(size, i - map.get(sum - k) + 1);
}
if (!map.containsKey(sum)) map.put(sum, i + 1);
}
return size;
}
}
Best time to sell stock
The points of interest are the peaks and valleys in the given graph. We need to find the largest peak following the smallest valley. We can maintain two variables - minprice and maxprofit corresponding to the smallest valley and maximum profit (maximum difference between selling price and minprice) obtained so far respectively.
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
// just maintain two variables maxprofit and minprice corresponding to
// the maximum of the profit and minimum of the price.
int maxprofit = 0, minprice = prices[0];
for (int i = 1; i < prices.length; ++i) {
maxprofit = Math.max(maxprofit, prices[i] - minprice);
minprice = Math.min(minprice, prices[i]);
}
return maxprofit;
}