Maximum Product Subarray
Find the contiguous subarray within an array(containig at least one number) which
has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray[2,3] has the
largest product = 6
An approach via dynamic programming
Need to keep in mind, while iterating the array, each element has two
possibilities: positive number or negative number. We need to track a min value so
that when a negative number is given, can also find the max value. We define two
local variables, one the max and one, the min
public int maxProduct(int[] nums){
int[] max = new int[nums.length];
int[] min = new int[nums.length];
max[0] = min[0] = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; i++){
if(nums[i] > 0){
max[i] = Math.max(nums[i], max[i-1]*nums[i]);
min[i] = Math.min(nums[i],min[i-1]*nums[i]);
} else {
max[i] = Math.max(nums[i],min[i-1]*nums[i]);
min[i] = Math.min(nums[i],max[i-1]*nums[i]);
}
result = Math.max(result,max[i]);
}
return result;
}
---------------------------------------------------
Given an array of non-negative integers, you are initially positioned at the first
index
of the array. Each element in the array represents your maximum jump length at that
position. Determine if you are able to reach the last index. For example: A =
[2,3,1,1,4],
return true. A = [3,2,1,0,4], return false.
Approach:
Track the max index that can be reached.In order to solve this problem:
do the foll:
1) When the current position cannot reach the next position in which case false is
returned
2) When the max index can reach the end return true in this case
The largest index that can be reached is i + A[i]
public boolean canJump(int[] A) {
if(A.length <= 1)
return true;
int max = A[0]; // max stands for the largest index that can be reached
for(int i = 0; i <= A.length; i++){
if(max <= i && A[i] == 0)
return false;
if(i + A[i] > max){
max = i + A[i];
}
if(max >= A.length-1)
return true;
}
return false;
}
