SDE - 1

A divide and conquer approach to solving the problem. The problem is a variation of the divide and conquer approach used to solve the "Maximum Subarray" problem. In addition to keeping track of the maximum positive product the maximum negative product of the divided regions also needs to be computed, since the product of two negative numbers is positive.

'''

class Solution {

int max(int a, int b) {

return Math.max(a, b);
}

int maxCrossing(int[] A, int low, int mid, int high) {

// Compute max positive and negative products left of mid
int maxPL = Integer.MIN_VALUE;
int maxNL = Integer.MAX_VALUE;
int prod = 1;
for(int i = mid; i >= low; --i) {
prod = prod * A[i];
if(prod > maxPL) {
maxPL = prod;
}
if(prod < maxNL) {
maxNL = prod;
}
}

// Compute max positive and negative products right of mid
int maxPR = Integer.MIN_VALUE;
int maxNR = Integer.MAX_VALUE;
prod = 1;
for(int i = mid + 1; i <= high; ++i) {
prod = prod * A[i];
if(prod > maxPR) {
maxPR = prod;
}
if(prod < maxNR) {
maxNR = prod;
}
}

// Compute max positive product crossing mid
int maxProd = max(maxPR, maxPL);
maxProd = max(maxProd, maxPR * maxPL);
maxProd = max(maxProd, maxNR * maxNL);

return maxProd;
}

int maxSubArray(int[] A, int low, int high) {
int res = 0;
if(low == high) {
return A[low];
}
int mid = (low + high) / 2;
// Compute max product subarray left of mid
int maxL = maxSubArray(A, low, mid);
// Compute max product subarray right of mid
int maxR = maxSubArray(A, mid + 1, high);
// Compute max product subarray crossing mid
int max_cross = maxCrossing(A, low, mid, high);

// Return max of all products
res = max(maxL, maxR);
res = max(res, max_cross);

return res;
}

public int maxProduct(int[] nums) {

int n = nums.length;

return maxSubArray(nums, 0, n - 1);
}
}

an easy solution :-

int findPeakElement(vector& nums)
{
int n = nums.size();
if(n==1)
return 0;
if(nums[0]>=nums[1])
return 0;
if(nums[n-1]>=nums[n-2])
return n-1;
for(int i = 1; i<=n-1;i++)
{
if(nums[i]>=nums[i-1] && nums[i]>=nums[i+1])
return i;
}

return -1;
}

class Solution {
public:

int numIslands(vector>& grid) {
int m = grid.size(), n = grid[0].size();
int ans = 0;
for(int i=0;i>& grid){
if(i < 0 || i>= grid.size() || j < 0 || j>= grid[0].size() || grid[i][j] != '1')
return;

grid[i][j] = '0';
dfs(i+1,j,grid);
dfs(i,j+1,grid);
dfs(i,j-1,grid);
dfs(i-1,j,grid);
}
};