Hi There

This is the first non algo post from my side.
If there are any good question which you think should be here kindly put a comment to this post along with your solution. We all can learn in this process.

Maximum Contiguous Subarray Product

An Array of N Elements are given which contains both +ve and -ve elements..
Find the Contiguous Subarray which contains the maximum Product.
P.S Neglect the Overflow and assume only integers are given as input.


Divide the array in groups with delimiters as zero. Now analyze each subgroup for number of nonnegative numbers.
If it is even then product of all numbers is the max of that subgroup otherwise
we have to divide the array in the following manner:
Let there be n+1 negative numbers where n +1 is odd,(o1,o2,o3....on) we have to include either {o1.....on } or {o2.....on+1} in the product and all the other positive numbers in between them.

Now using the above logic we get the max of that sub group. We iterate over all other subsets to determine the maximum among them.

Array Difference

Given an array of size n.find 2 numbers from array whose difference is least.

Solution:

Sort the list and substract consecutive numbers to get the smallest difference.

Time : O(nlogn)