I appeared for the test. Was able to solve all the test cases using Kadane's algorithm. The thing to notice is that the max value can be achieved by multiplying (Maximum Sum Subarray)(Maximum element of that subarray) OR (Minimum Sum Subarray)(Minimum element of that subarray). The second case is because multiplying two negative values produces a positive value. This can be achieved in O(N) by Kadane's algo. Below is the code which passed all 15 test cases.
`
public static long maxStock(List<Integer> stockValue) {
int n=stockValue.size();
int[] arr = new int[n];
int i=0;
for(int x:stockValue) {
arr[i]=x;
i++;
}
return Math.max(maxSubArraySum(arr),minSubArraySum(arr));
}
static long maxSubArraySum(int a[]) {
long size = a.length;
long max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
long maxE = Integer.MIN_VALUE;
long ansMax = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
maxE = Math.max(maxE, a[i]);
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
ansMax = Math.max(ansMax, max_so_far * maxE);
}
if (max_ending_here < 0) {
max_ending_here = 0;
maxE = Integer.MIN_VALUE;
}
}
return ansMax;
}
static long minSubArraySum(int a[]) {
long size = a.length;
long min_so_far = Integer.MAX_VALUE, min_ending_here = 0;
long minE = Integer.MAX_VALUE;
long ansMin = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
min_ending_here = min_ending_here + a[i];
minE = Math.min(minE, a[i]);
if (min_so_far > min_ending_here) {
min_so_far = min_ending_here;
ansMin = Math.max(ansMin, min_so_far * minE);
}
if (min_ending_here > 0) {
min_ending_here = 0;
minE = Integer.MAX_VALUE;
}
}
return ansMin;
}