Amazon Interview Question
Country: India
Have tested for following inputs:---
int[] ints = new int[] {6, 7, 8, 1, 2, 3, 9, 10};
int[] ints = new int[] {4, 7, 9, 8, 2};
int[] ints = new int[] {1, 11, 12, 7, 8, 9};
int[] ints = new int[] {1, 4, 2, 3};
int[] ints = new int[]{1, 11, 8, 9, 10, 14};
int[] ints = new int[]{10, 6, 11};
int[] ints = new int[]{1, 5, 10, 8, 9};
Time Complexity: O(n), Space Complexity: O(n)
Store maximum indexes of left sub array and right sub array for each index and multiply them.
public static int[] findSubsequenceWithMaxProduct(int data[]){
int[] subsequence = new int[3];
int leftMaxIndex[] = new int[data.length];
int rightMaxIndex[] = new int[data.length];
leftMaxIndex[0] = 0;
for(int index = 1; index < leftMaxIndex.length; index++){
if(data[leftMaxIndex[index - 1]] < data[index]){
leftMaxIndex[index] = index;
} else{
leftMaxIndex[index] = leftMaxIndex[index - 1];
}
}
rightMaxIndex[rightMaxIndex.length - 1] = data.length - 1;
for(int index = rightMaxIndex.length - 2; index >= 0; index--){
if(data[rightMaxIndex[index + 1]] < data[index]){
rightMaxIndex[index] = index;
} else{
rightMaxIndex[index] = rightMaxIndex[index + 1];
}
}
int maxProduct = Integer.MIN_VALUE;
int currentProduct = 0;
for(int index = 1; index <data.length - 1; index++){
if(data[leftMaxIndex[index-1]] <= data[index] && data[index] <= data[rightMaxIndex[index+1]]){
currentProduct = data[leftMaxIndex[index-1]] * data[index] * data[rightMaxIndex[index+1]];
if(currentProduct > maxProduct){
maxProduct = currentProduct;
subsequence = new int[]{data[leftMaxIndex[index-1]], data[index], data[rightMaxIndex[index+1]]};
}
}
}
return subsequence;
}
One solution can be modification of code from algorithmist.com/index.php/Longest_Increasing_Subsequence.cpp to get max product of increasing sub-sequence of 3.
#include <vector>
using namespace std;
#define INT_MIN -(1 << 30)
void find_lis(vector<int> &a, vector<int> &c)
{
vector<int> p(a.size());
vector<int> b(a.size());
int u, v;
int max_product_seen = INT_MIN;
int curr_product = INT_MIN;
if (a.empty()) return;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++)
{
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
if (b.size() >=3)
{
curr_product = a[b[b.size()-1]] * a[b[b.size()-2]] * a[b[b.size()-3]];
if (curr_product > max_product_seen) {
max_product_seen = max_product_seen;
while (!c.empty())
c.pop_back();
c.push_back(a[b[b.size()-3]]);
c.push_back(a[b[b.size()-2]]);
c.push_back(a[b[b.size()-1]]);
}
}
// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size()-1; u < v;)
{
int m = (u + v) / 2;
if (a[b[m]] < a[i]) u=m+1; else v=m;
}
// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]])
{
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
if (b.size() >=3)
{
curr_product = a[b[b.size()-1]] * a[b[b.size()-2]] * a[b[b.size()-3]];
if (curr_product > max_product_seen) {
max_product_seen = max_product_seen;
while (!c.empty())
c.pop_back();
c.push_back(a[b[b.size()-3]]);
c.push_back(a[b[b.size()-2]]);
c.push_back(a[b[b.size()-1]]);
}
}
}
// some correction
#include <vector>
using namespace std;
#define INT_MIN -(1 << 30)
void find_lis(vector<int> &a, vector<int> &c)
{
vector<int> p(a.size());
vector<int> b(a.size());
int u, v;
int max_product_seen = INT_MIN;
int curr_product = INT_MIN;
if (a.empty()) return;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++)
{
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
if (b.size() >=3)
{
curr_product = a[b[b.size()-1]] * a[b[b.size()-2]] * a[b[b.size()-3]];
if (curr_product > max_product_seen) {
max_product_seen = max_product_seen;
while (!c.empty())
c.pop_back();
c.push_back(a[b[b.size()-3]]);
c.push_back(a[b[b.size()-2]]);
c.push_back(a[b[b.size()-1]]);
}
}
continue;
}
// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size()-1; u < v;)
{
int m = (u + v) / 2;
if (a[b[m]] < a[i]) u=m+1; else v=m;
}
// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]])
{
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
if (b.size() >=3)
{
curr_product = a[b[b.size()-1]] * a[b[b.size()-2]] * a[b[b.size()-3]];
if (curr_product > max_product_seen) {
max_product_seen = max_product_seen;
while (!c.empty())
c.pop_back();
c.push_back(a[b[b.size()-3]]);
c.push_back(a[b[b.size()-2]]);
c.push_back(a[b[b.size()-1]]);
}
}
}
Complexity: O(N^2)
Steps:
1) Pick the first number and try to find two maximum numbers to its right in increasing order,
2) if Found , store the product of all three numbers
3) do this for all numbers
well it can be improved furthure , once we got a triplet a1<a2<a3, we can skip these test for any b right of a1 and left of a2 where b<a1.
public int getMaxProd(int[] nums){
if(nums == null || nums.length < 3 ){
return -1;
}
int maxProdSoFar = 0;
for(int i=0; i<nums.length; i++){
int pivot = nums[i];
int localMax = pivot*getProdOfTwoLargest(nums,i+1,nums.length-1, pivot);
if(localMax > maxProdSoFar){
maxProdSoFar = localMax;
}
}
return maxProdSoFar;
}
public int getProdOfTwoLargest(int[] nums, int startIndex, int endIndex, int pivot){
int firstLargest = -1;
int secondLargest = -1;
// largest has to be in contiguous manner
for (int i=startIndex; i<=endIndex; i++){
if ( (nums[i] > pivot) && (nums[i] > firstLargest)){
secondLargest = firstLargest;
firstLargest = nums[i];
}
}
if(firstLargest == -1 || secondLargest == -1){
return 0;
}
return firstLargest*secondLargest;
}
getProdOfTwoLargest fails with this:
nums = [1, 3, 2, 10, 8, 9]
startIndex = 1
endIndex = 5
pivot = 2
It returns 30 instead of 72.
An interesting solution might be to sort those elements beforehand keep the indexes and look to the index table to find the max element. So step by step:
1. Sort the array. Keep which element was at which index. (That is O(NlogN) time computation plus O(2N) space for but the current array and the index table)
So if we have an input like this: {1, 11, 12, 7, 6, 8, 9}
we will have a sorted array like: {1, 7, 6, 8, 9, 11, 12}
obviously and we will also have an indices array such as this: {0, 4, 3, 5, 6, 1, 2} (the index of 12 at the end of the sorted array had an index of 2 in the original array and so an.)
2. From the highest element in the sorted array, start finding highest 3 elements. Something like:
int[] current_triple = new int[3];
max_product = 1;
for (int i = n -1; i > 1; i--) {
int[] triples = new int[3];
triples.insert(i)
for (int k = i - 1; k >= 0; k--) {
//If the index of the previous element in the array is lesser then element I'm looking that I add it to the threeway array
if (indices[k] < indices[i]) {
triples.insert(k)
}
if (triples.length > 2) {
//Ok so I found the best triple available for this one.
// The array was already sorted so, I already found the highest triple in ascending order
break;
}
}
if (triples.length != 3) {
//Ignore this case as there is no valid triple
continue;
}
int tmp_product = triples[0] * triples[1] * triples[2];
if (tmp_product > max_product) {
max_product = tmp_product;
current_triple = triples;
}
}
3. In the end just print the current_triple array.
This is an O(NlgN + N^2) computation and O(2N) space complexity solution. However if we find a faster way of traversing the index array, it might become faster.
But maybe I'm missing something out.
Since the code was not complete, I completed it. It's a bit messy but works:
package Main;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
public class Main {
public static List<Integer> findMaxProductFromArray(int[] inputArray){
int n = inputArray.length;
int[] indices = new int[n];
Integer[] originalInput = new Integer[inputArray.length];
int i = 0;
for (int value : inputArray) {
originalInput[i++] = Integer.valueOf(value);
}
Arrays.sort(inputArray);
for (i = 0; i < n ; i++) {
indices[i] = Arrays.asList(originalInput).indexOf(inputArray[i]);
}
List<Integer> current_triple = new ArrayList<Integer>();
int max_product = 1;
for (i = n-1 ; i > 1 ; i--) {
List<Integer> triples = new ArrayList<Integer>();
triples.add(inputArray[i]);
for (int k = i - 1; k >= 0; k--) {
//If the index of the previous element in the array is lesser then element I'm looking that I add it to the threeway array
if (indices[k] < indices[i]) {
triples.add(inputArray[k]);
}
if (triples.size() > 2) {
//Ok so I found the best triple available for this one.
// The array was already sorted so, I already found the highest triple in ascending order
break;
}
}
if (triples.size() != 3) {
//Ignore this case as there is no valid triple
continue;
}
int tmp_product = triples.get(0) * triples.get(1) * triples.get(2);
if (tmp_product > max_product) {
max_product = tmp_product;
current_triple = triples;
}
}
return current_triple;
}
public static void main(String[] args) {
int input[] = {6,7,8,1,2,3,9,10};
System.out.println(findMaxProductFromArray(input));
}
}
and here is the code in Ruby (much cleaner):
def find_max_product(input_array)
sorted_input_array = input_array.sort
indices = []
sorted_input_array.each do |number|
indices.push(input_array.index(number))
end
current_triple = []
max_product = 1
(input_array.length - 1).downto(0) do |i|
triples = [sorted_input_array[i]]
(i-1).downto(0) do |k|
if indices[k] < indices[i]
triples.push(sorted_input_array[k])
end
if triples.length > 2
break
end
end
if triples.length != 3
next
end
tmp_product = triples.inject(:*)
if tmp_product > max_product
max_product = tmp_product
current_triple = triples
end
end
current_triple.reverse
end
puts find_max_product([1, 5, 10, 8, 9])
I completed the code:
package Main;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
public class Main {
public static List<Integer> findMaxProductFromArray(int[] inputArray){
int n = inputArray.length;
int[] indices = new int[n];
Integer[] originalInput = new Integer[inputArray.length];
int i = 0;
for (int value : inputArray) {
originalInput[i++] = Integer.valueOf(value);
}
Arrays.sort(inputArray);
for (i = 0; i < n ; i++) {
indices[i] = Arrays.asList(originalInput).indexOf(inputArray[i]);
}
List<Integer> current_triple = new ArrayList<Integer>();
int max_product = 1;
for (i = n-1 ; i > 1 ; i--) {
List<Integer> triples = new ArrayList<Integer>();
triples.add(inputArray[i]);
for (int k = i - 1; k >= 0; k--) {
//If the index of the previous element in the array is lesser then element I'm looking that I add it to the threeway array
if (indices[k] < indices[i]) {
triples.add(inputArray[k]);
}
if (triples.size() > 2) {
//Ok so I found the best triple available for this one.
// The array was already sorted so, I already found the highest triple in ascending order
break;
}
}
if (triples.size() != 3) {
//Ignore this case as there is no valid triple
continue;
}
int tmp_product = triples.get(0) * triples.get(1) * triples.get(2);
if (tmp_product > max_product) {
max_product = tmp_product;
current_triple = triples;
}
}
return current_triple;
}
public static void main(String[] args) {
int input[] = {6,7,8,1,2,3,9,10};
System.out.println(findMaxProductFromArray(input));
}
}
Here is a possible solution:
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int *a, n=0;
int b[3];
int c[3];
int prod, maxprod=0, k=0, j;
cin>>n;
a= new int [n];
for(int i=0; i<n; i++)
cin>>a[i];
for (int i=0; i<n-2; i++){
prod=a[i];
j=i+1;
k=0;
b[0]=i;
while(k<2 && j<n)
if(a[b[k]]<a[j] )
{prod*=a[j];
k++;
b[k]=j;
j++;
}
else j++;
if(k==2 && maxprod < prod)
{
maxprod=prod;
c[0]=b[0]; c[1]=b[1]; c[2]=b[2];
}
}
cout<<a[c[0]]<<" "<<a[c[1]]<<" "<<a[c[2]];
getch();
return 0;
}
Any suggestions would be helpful !
The numbers will be stored in a,b and c.
void find_numbers(int array[], int n, int* a, int* b, int* c)
{
int* less = new int[n];
int* more = new int[n];
less[0] = -1;
more[n-1] = -1;
for(int i = 1; i < n; i++)
{
less[i] = INT_MIN;
for(int j = i-1; j >= 0; j--)
{
if((array[j] < array[i]) && (array[j] > less[i]))
less[i] = array[j];
}
}
for(int i = n-2; i >= 0; i--)
{
more[i] = array[i];
for(int j = i+1; j < n; j++)
{
if((array[i] < array[j]) && (more[i] < array[j]))
more[i] = array[j];
}
}
int product = 0;
for(int i = 0; i < n; i++)
{
if(less[i]*array[i]*more[i] > product)
{
*a = less[i];
*b = array[i];
*c = more[i];
}
}
}
here the logic is simple:
scan the array from right to left.
find the biggest number in the array and remember it.
find second largest number to the left of first and remember it.
find third largest number to the left of second and remember it.
update maximum product when found a bigger product.
let the inputs are in an array A of size n
1. init result[3] with 0 /* for final result */
2. init maximum_product with 0
3. init temp[3] with 0 /* for temporary results. */
4. for i <- n to 1
5. if (A[i] > temp[3]) /* this is the highest number found so far. */
6. temp[3] <- A[i]
7. temp[2] <- 0
8. temp[1] <- 0
9. else
10. if (A[i] > temp[2])
11. temp[1] <- 0
12. temp[2] <- A[i]
13. else if (A[i] > temp[1])
14. temp[1] <- A[i]
15. if (temp[1] * temp[2] * temp[3] > maximum_product)
14. maximum_product <- temp[1] * temp[2] * temp[3]
15. result[1] <- temp[1]
16. result[2] <- temp[2]
17. result[3] <- temp[3]
18. /* end of for loop*/
19. if (result[1] && result[2] && result[3])
20. print result[1] && result[2] && result[3]
21. else print "no solution found"
@Anonymous - if first element is largest, as per the question, there is no solution since there is no second and third largest nos left to first array element.
@m3th0d.itbhu - step 14 to 17 will be executed only once for your input. That is when A[i] is 7. Then how the output will be 1*11*12 ???
here the sequence is not maintained
for eg: ip 10 6 11,
required: no sequence found
it outputs: 6*10*11
O(n) is possible.
Input: 6 7 8 1 2 3 9 10
Program:
int f,s,t = a[0];
for(int i=0;i<n;i++)
{
if(t<a[1+1])
{
f=s;
s=t;
t=a[i+1];
}
}
Print f,s,t;
Minor change in my above program. Replacing n with n-1
Input1: 6 7 8 1 2 3 9 10
Input 2: 4, 7, 9, 8, 2
Program:
int f,s,t = a[0];
for(int i=0;i<n-1;i++)
{
if(t<a[1+1])
{
f=s;
s=t;
t=a[i+1];
}
}
Print f,s,t;
I assume you mean i+1 instead of 1+1. However, even then the code does not work as it simply chooses the first rather than the largest sequence. For example take the sequence 1,9,7,8,10,9. Your solution produces 1,9,10, whereas the correct answer is 7,8,10.
// Find_Max_Product.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
int find_Min(int result[])
{
int min;
int min_index;
if(result[0]<result[1])
{
if(result[0]<result[2])
{
min=result[0];
min_index=0;
}
else
{
min=result[2];
min_index=2;
}
}
else
{
if(result[1]<result[2])
{
min=result[1];
min_index=1;
}
else
{
min=result[2];
min_index=2;
}
}
return min_index;
}
int findMaxProduct(int arr[],int len)
{
int result[3];
if(len<3)
return -1;
if(len==3)
return *arr;
result[0]=arr[0];
result[1]=arr[1];
result[2]=arr[2];
int min_index=find_Min(result);
int min=result[min_index];
for(int i=3;i<len;i++)
{
for(int j=0;j<3;j++)
{
if(arr[i]>result[j])
{
min_index=find_Min(result);
result[min_index]=arr[i];
break;
}
}
}
std::cout<<"output";
for(int i=0;i<3;i++)
{
std::cout<<result[i]<<" ";
}
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[13]={6,7,8,1,2,3,9,10,2,5,12,15};
findMaxProduct(arr,13);
return 0;
}
O(n2) solution:
findMaxProd(int[] a)
int ret = 0;
for(int i=0;i<n;i++){
int k=i+1, count=1, prod=a[i], prev=i;
while(k<n && count < 3){
if(a[k] > a[prev])
{
prod *= a[k]; count++; prev = k;
}
k++;
}
if(count == 3)
ret = Math.max(prod, ret);
}
return ret;
I don't think your solution is correct. Consider the case {1, 4, 2, 3}
The solution is 1, 2, 3 but your code won't find it because it is looking for the first ascending number after the max so far.
It starts with 1, then finds 4 and goes {1, 4} but nothing in the set is greater than 4 so it skips over 1 as the start of a sequence and returns no solution.
int find_Min(int result[])
{
int min;
int min_index;
if(result[0]<result[1])
{
if(result[0]<result[2])
{
min=result[0];
min_index=0;
}
else
{
min=result[2];
min_index=2;
}
}
else
{
if(result[1]<result[2])
{
min=result[1];
min_index=1;
}
else
{
min=result[2];
min_index=2;
}
}
return min_index;
}
int findMaxProduct(int arr[],int len)
{
int result[3];
if(len<3)
return -1;
if(len==3)
return *arr;
result[0]=arr[0];
result[1]=arr[1];
result[2]=arr[2];
int min_index=find_Min(result);
int min=result[min_index];
for(int i=3;i<len;i++)
{
for(int j=0;j<3;j++)
{
if(arr[i]>result[j])
{
min_index=find_Min(result);
result[min_index]=arr[i];
break;
}
}
}
std::cout<<"output";
for(int i=0;i<3;i++)
{
std::cout<<result[i]<<" ";
}
return 1;
}
public class FindMaxProduct
{
private static List<Integer> input_ = new ArrayList<Integer>(Arrays.asList(6,7,8,1,2,3,9,10));
private static List<Integer> prodList_ = new ArrayList<Integer>();
public static void main(String[] args)
{
for(int i=0;i<input_.size();i++) {
int currentValue = input_.get(i);
//System.out.println(currentValue);
Collections.sort(prodList_);
if (prodList_.size() < 3) {
prodList_.add(currentValue);
}
else {
if (currentValue >= prodList_.get(0)) {
prodList_.set(0, currentValue);
}
}
}
Collections.sort(prodList_);
for (int i=0;i<prodList_.size();i++) {
System.out.println(prodList_.get(i));
}
}
}
package General;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindMaxProductSequence {
public static List<Integer> find(List<Integer> input)
{
List<Integer> prodList_ = new ArrayList<Integer>();
int maxProd = 1;
int index = 0;
for (int i = 0 ; i < input.size()-2;i++)
{
if(maxProd < findProduct(i, input))
{
maxProd = findProduct(i, input);
index = i ;
}
}
prodList_.add(input.get(index));
prodList_.add(input.get(index+1));
prodList_.add(input.get(index+2));
return prodList_;
}
private static Integer findProduct(int i,List<Integer>input)
{
return input.get(i)*input.get(i+1)*input.get(i+2);
}
public static void main(String[] args) {
List<Integer> input_ = new ArrayList<Integer>(Arrays.asList(6,7,8,1,2,3,11,9,10));
List<Integer> out = FindMaxProductSequence.find(input_);
for(int i : out)
{
System.out.println(i);
}
}
}
public static void main(String args[]){
int[] sat = {6,7,8,1,2,3,9,10};
int temp = sat[0];
for(int i=0;i<sat.length;i++){
for(int j=0;j<sat.length-1;j++){
if(sat[j]>sat[j+1]){
temp = sat[j];
sat[j]=sat[j+1];
sat[j+1]=temp;
}
}
}
int sat1 = sat.length - 3;
for(int k=sat1;k<sat.length;k++){
System.out.print(sat[k] + " ");
}
}
I believe in this problem we need not worry about the product as the product of the maximum 3 numbers will be greater than any other 3 numbers. Hence the problem reduces to finding the max 3 numbers in ascending order. This is my code in C#. Please let me know if I am wrong somewhere. Thanks.
class SequenceNumbers
{
public List<int> GenerateSub(int[] input)
{
int iMax = input[0];
List<int> oList = new List<int>();
List<int> oFinalList = new List<int>();
oList.Add(iMax);
for (int i = 1; i < input.Length; i++)
{
if (iMax < input[i])
{
oList.Add(input[i]);
iMax = input[i];
//continue;
}
}
if (oList.Count > 1)
{
for (int i = 3; i > 0; i--)
{
oFinalList.Add(oList[oList.Count - i]);
}
}
return oFinalList;
}
}
I think you need to check for iMax <= input[i] in case the array has duplicates. Also, at the end check that the list is atleast 3 elements long or you get incorrect answer
I think this is O(n^2).Just search for highest, second highest and third highest in the array as that will give the maximum product.
#include <stdio.h>
int main()
{
int a[] = {4, 5, 6, 7, 3, 10, 11};
int first=-1;int second=-1;int third=-1;
int t_f, t_s, i;
if((sizeof(a)/sizeof(a[0])-1 <= 3))
printf("what the hell?\n");
if(first == -1)
first = a[0];
for(i=0;i<sizeof(a)/sizeof(a[0])-1;i++) {
if(a[i+1] > a[i]) {
t_f = first;
first = a[i+1];
if(second == -1) {
second = a[i];
} else {
t_s = second;
second = t_f;
third = t_s;
}
}
}
printf("first %d secodn %d third %d\n", first, second, third);
return 0;
}
class MaximumProduct{
public int[] subsequenceOfThreeNumbersHavingMaximumProduct(int[] series) {
int result[] = { 0, 0, 0 };
if (series.length < 3) {
return series;
}
result = keepOrdering(result, series[0]);
result = keepOrdering(result, series[1]);
result = keepOrdering(result, series[2]);
for (int i = 3; i < series.length; i++) {
result = keepOrdering(result, series[i]);
}
return result;
}
public int[] keepOrdering(int[] result, int newelt) {
if (newelt >= result[2]) {
result[0] = result[1];
result[1] = result[2];
result[2] = newelt;
} else if (newelt < result[2] && newelt >= result[1]) {
result[0] = result[1];
result[1] = newelt;
} else if (newelt < result[1] && newelt >= result[0]) {
result[0] = newelt;
}
return result;
}
}
C# Code:
--------------------
using System;
using System.Linq;
using System.Collections.Generic;
namespace MaxProdForThreeAscendingNumbersInArray
{
class Program
{
private static IList<int> Arr;
private static IDictionary<ProdInput, ProdOutput> ProdCache;
private static int subseqLen = 3;
struct ProdInput
{
public int curIndex;
public int numbersLeft;
public int minValue;
public ProdInput(int p1, int p2, int p3)
{
curIndex = p1;
numbersLeft = p2;
minValue = p3;
}
}
struct ProdOutput
{
public int Value;
public Stack<int> Subseq;
public ProdOutput(int val, Stack<int> SubseqIn)
{
Value = val;
Subseq = new Stack<int>(SubseqIn);
}
}
static void Main(string[] args)
{
if (0 == args.Length)
{
Console.WriteLine("ERROR: Enter array.\n"
+"USAGE: exe 4 2 5 8 10 ");
return;
}
Arr = new List<int>();
ProdCache = new Dictionary<ProdInput, ProdOutput>();
PopulateInputArray(args);
DisplayInputArray();
ProdOutput Output = ComputeMaxProd();
Console.Write("Max product: ");
if(Output.Value == -1)
{
Console.Write("No subsequence found!");
}
else
{
Console.Write(Output.Value);
Console.WriteLine("");
foreach (var element in Output.Subseq.Reverse())
{
Console.Write(" {0}", element);
}
}
}
private static ProdOutput ComputeMaxProd()
{
return Prod(0, //curIndex
subseqLen, //numbersLeft
0 //minValue
);
}
private static ProdOutput Prod(int curIndex, int numbersLeft, int minValue)
{
if (0 == numbersLeft)
{
return new ProdOutput(1, new Stack<int>());
}
if (curIndex >= Arr.Count)
{
return new ProdOutput(-1, new Stack<int>());
}
ProdInput curInput = new ProdInput(curIndex, numbersLeft, minValue);
ProdOutput curOutput;
if (!ProdCache.ContainsKey(curInput))
{
if (Arr[curIndex] >= minValue)
{
ProdOutput withElem = Prod(curIndex + 1, numbersLeft - 1, Arr[curIndex]);
withElem.Value *= Arr[curIndex];
ProdOutput withoutElem = Prod(curIndex + 1, numbersLeft, minValue);
if (withElem.Value > withoutElem.Value)
{
withElem.Subseq.Push(Arr[curIndex]);
ProdCache[curInput] = withElem;
}
else
{
ProdCache[curInput] = withoutElem;
}
}
else
{
ProdCache[curInput] = Prod(curIndex + 1, numbersLeft, minValue);
}
}
curOutput = new ProdOutput(ProdCache[curInput].Value, ProdCache[curInput].Subseq);
return curOutput;
}
private static void DisplayInputArray()
{
Console.Write("Input Array:");
foreach (var element in Arr)
{
Console.Write(" {0}", element);
}
Console.WriteLine("");
}
private static void PopulateInputArray(string[] args)
{
foreach (var input in args)
{
Arr.Add(Int32.Parse(input));
}
}
}
}
C# Code:
--------------------
using System;
using System.Linq;
using System.Collections.Generic;
namespace MaxProdForThreeAscendingNumbersInArray
{
class Program
{
private static IList<int> Arr;
private static IDictionary<ProdInput, ProdOutput> ProdCache;
private static int subseqLen = 3;
struct ProdInput
{
public int curIndex;
public int numbersLeft;
public int minValue;
public ProdInput(int p1, int p2, int p3)
{
curIndex = p1;
numbersLeft = p2;
minValue = p3;
}
}
struct ProdOutput
{
public int Value;
public Stack<int> Subseq;
public ProdOutput(int val, Stack<int> SubseqIn)
{
Value = val;
Subseq = new Stack<int>(SubseqIn);
}
}
static void Main(string[] args)
{
if (0 == args.Length)
{
Console.WriteLine("ERROR: Enter array.\n"
+"USAGE: exe 4 2 5 8 10 ");
return;
}
Arr = new List<int>();
ProdCache = new Dictionary<ProdInput, ProdOutput>();
PopulateInputArray(args);
DisplayInputArray();
ProdOutput Output = ComputeMaxProd();
Console.Write("Max product: ");
if(Output.Value == -1)
{
Console.Write("No subsequence found!");
}
else
{
Console.Write(Output.Value);
Console.WriteLine("");
foreach (var element in Output.Subseq.Reverse())
{
Console.Write(" {0}", element);
}
}
}
private static ProdOutput ComputeMaxProd()
{
return Prod(0, //curIndex
subseqLen, //numbersLeft
0 //minValue
);
}
private static ProdOutput Prod(int curIndex, int numbersLeft, int minValue)
{
if (0 == numbersLeft)
{
return new ProdOutput(1, new Stack<int>());
}
if (curIndex >= Arr.Count)
{
return new ProdOutput(-1, new Stack<int>());
}
ProdInput curInput = new ProdInput(curIndex, numbersLeft, minValue);
ProdOutput curOutput;
if (!ProdCache.ContainsKey(curInput))
{
if (Arr[curIndex] >= minValue)
{
ProdOutput withElem = Prod(curIndex + 1, numbersLeft - 1, Arr[curIndex]);
withElem.Value *= Arr[curIndex];
ProdOutput withoutElem = Prod(curIndex + 1, numbersLeft, minValue);
if (withElem.Value > withoutElem.Value)
{
withElem.Subseq.Push(Arr[curIndex]);
ProdCache[curInput] = withElem;
}
else
{
ProdCache[curInput] = withoutElem;
}
}
else
{
ProdCache[curInput] = Prod(curIndex + 1, numbersLeft, minValue);
}
}
curOutput = new ProdOutput(ProdCache[curInput].Value, ProdCache[curInput].Subseq);
return curOutput;
}
private static void DisplayInputArray()
{
Console.Write("Input Array:");
foreach (var element in Arr)
{
Console.Write(" {0}", element);
}
Console.WriteLine("");
}
private static void PopulateInputArray(string[] args)
{
foreach (var input in args)
{
Arr.Add(Int32.Parse(input));
}
}
}
}
public class Common {
public static void main(String args[]) {
int a[] = { 4, 7, 9, 8, 2 };
int[] b = new int[3];
int index = a.length - 1;
for (int j = 0; j < 3; j++) {
if (j != 0)
index--;
for (int i = index; i >= 0; i--) {
if (a[i] > b[j]) {
index = i;
b[j] = a[i];
}
}
}
System.out.print(b[2] + " " + b[1] + " " + b[0]);
}
}
vector<int> Find_pro(int a[],int size){
vector<int> p;
p.clear();
int product=0;
for(int i=0;i<size;i++){
int f=a[i];
int s=a[i];
int t=a[i];
for(int j=i;j<size;j++){
if(a[j]>t){
f=s;
s=t;
t=a[j];
}
}
if(s!=f&&f*s*t>product){
product=f*s*t;
p.clear();
p.push_back(f);
p.push_back(s);
p.push_back(t);
}
}
return p;
}
C++ version
I have a java version for O(n^2) at worst case
public class MaxProductOfThree {
public static void getMaxProduct(int[] array){
ArrayList<ArrayList<Integer>> sequences = new ArrayList<ArrayList<Integer>>();
//find all the possible ascending sequences
for(int i=0;i<array.length;i++){
boolean added = false;
for(int j=0;j<sequences.size();j++){
ArrayList<Integer> seq = sequences.get(j);
if(array[i] > seq.get(seq.size()-1)){
seq.add(array[i]);
added = true;
}
}
//if not added to any sequence, means it's a starting number for a new sequence
if(added == false){
ArrayList<Integer> newSeq = new ArrayList<Integer>();
newSeq.add(array[i]);
sequences.add(newSeq);
}
}
int maxProduct = 0;
int[] result = new int[3];
//go thru the last 3 elements of all the ascending sequences, find the max product
for(int j=0;j<sequences.size();j++){
ArrayList<Integer> seq = sequences.get(j);
int s = seq.size();
if(s >= 3){
int product = seq.get(s-3) * seq.get(s-2) * seq.get(s-1);
if(product > maxProduct){
maxProduct = product;
result[0] = seq.get(s-3);
result[1] = seq.get(s-2);
result[2] = seq.get(s-1);
}
}
}
System.out.println("The result is: "+result[0]+", "+result[1]+", "+result[2]);
}
public static void main(String[] args) {
// int[] array = {6,7,8,1,2,3,9,10};
int[] array = {2,3,8,6,7,9};
getMaxProduct(array);
}
}
Complexity : O (n)
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n, i;
int prod;
int max_prod = 0;
int n1, n2, n3;
printf("How many numbers ?: ");
scanf("%d",&n);
int *p = (int*)malloc(n * sizeof(int));
printf("Enter %d numbers\n",n);
for(i = 0; i < n; i++)
scanf("%d",&p[i]);
for(i = 0; i < n;)
{
if (p[i] < p[i+1] && p[i + 1] < p[i + 2])
{
prod = p[i] * p[i+1] * p[i+2];
if (prod > max_prod)
{
n1 = p[i]; n2 = p[i+1]; n3 = p[i+2];
max_prod = prod;
}
i = i +1;
}
else if (p[i] > p[i+1] && p[i+1] < p[i+2])
{
i = i + 1;
}
else
{
i = i + 2;
}
}
printf("\n Set is (%d, %d, %d)\nProduct = %d\n",n1,n2,n3,max_prod);
return 0;
}
public static int findMaxProd(int[] array) {
// 4, 7, 6, 8, 10, 2, 3, 11
//8,10,11
if (array.length < 3) return 0;
int[] result = new int[3];
Arrays.fill(result, 0);
for (int i = 0; i < array.length; i++) {
if (array[i] > result[2]) {
if (array[i] > result[2]) {
//rotate the elements
result[0] = result[1];
result[1] = result[2];
result[2] = array[i];
} else if (array[i] > result[1]) {
result[0] = result[1];
result[1] = result[2];
} else if (array[i] > result[0]) {
result[0] = array[i];
}
}
}
return result[0] * result[1] * result[2];
}
public static void max3(int[] arr)
{
int max1 = arr[0];
int max2 = arr[0];
int max3 = arr[0];
for(int i = 1; i< arr.length; i++)
{
if(arr[i] > max3)
{
max1 = max2;
max2 = max3;
max3 = arr[i];
}
else if(arr[i] > max2)
{
max1 = max2;
max2 = arr[i];
}
else if(arr[i] > max1)
{
max1 = arr[i];
}
}
System.out.println(max1+ "," + max2 + "," + max3);
}
I think this should work in o(n). Not fully tested.. might miss some corner cases..
package ArrayImpl;
public class MaxProductinSubSequence {
/**
* Given a sequence of non-negative integers find a subsequence of length 3
* having maximum product with the numbers of the subsequence being in ascending order.
* Example:
* Input: 6 7 8 1 2 3 9 10
* Ouput: 8 9 10
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int input[] = {6,7,8,1,2,3,9,10};
int x1, x2, x3; x1 = x2 = x3 = input[0];
for (int i = 1; i < input.length; i++)
{
System.out.println(input[i]+ ":::" + x1 + " " + x2 + " " + x3);
x3 = x3 < x2 && x3 < input[i]? x2 < input[i]? x2 : input[i] : x3;
x2 = x2 < x1 && x2 < input[i]? x1 < input[i]? x1 : input[i] : x2;
x1 = x1 < input[i] ? input[i] : x1;
System.out.println(input[i]+ ":::" + x1 + " " + x2 + " " + x3);
}
if (x1 == x2 || x2 == x3 || x3 == x1)
System.out.println("No Such Product");
else
System.out.println(x1 + " * " + x2 + " * " + x3 + " = " + x1*x2*x3 );
}
}
Logic:
Let array index start from 0 to n-1 (where n is the number of elements).
Let i = n - 1
Step 1. Find the largest number from index = i to index = 2, let position of the number (n1) found = pos1
Step2. Find the largest number from index = pos1 - 1 to index = 1, let position of the number (n2) found = pos2
Step3. Find the largest number form index = pos2 - 1 to index = 0. Let the position of the number (n3) found = pos3
Step4. if n1 > n2 and n2 > n3 then find the product n1 * n2 * n3.
Step5. If product is more then the prev. product (i.e. max_prod), update max_prod
Step6. Do i-- and repeat step 1 to step 6 till i >= 2
Step 7. Required result is stored in max_prod.
#include<stdio.h>
#include<stdlib.h>
int FindLargest(int *p, int start, int end, int *pos);
int main()
{
int n;
int i;
int pos1 = -1, pos2 = -1, pos3 = -1;
int n1, n2, n3;
int max_prod = 0, prod;
printf("How many numbers ? ");
scanf("%d",&n);
int *a = (int*)malloc(n * sizeof(int));
printf("Enter the %d numbers :\n",n);
for(i = 0; i < n; i++){
scanf("%d",&a[i]);
}
for(i = n-1; i >=2; i--)
{
//find the first number
n1 = FindLargest(a,i,2, &pos1);
printf("n1 = %d, pos1 = %d\n", n1, pos1);
n2 = FindLargest(a,pos1-1,1, &pos2);
printf("n2 = %d, pos2 = %d\n", n2, pos2);
n3 = FindLargest(a,pos2-1,0, &pos3);
printf("n3 = %d, pos3 = %d\n", n3, pos3);
if (n1 > n2 && n2 > n3)
{
prod = n1 * n2 * n3;
if (prod > max_prod)
{
max_prod = prod;
printf("max_prod = %d", max_prod);
}
}
}
printf("max product is %d \n", max_prod);
return 0;
}
int FindLargest(int *p, int start, int end, int *pos)
{
int i;
int max = 0;
for (i = start; i >= end; i--)
{
if (max < p[i])
{
max = p[i];
*pos = i;
}
}
return max;
}
Hi All
This is not too difficult. To note, an increasing sequence of three numbers that when multiplied yields the highest result is merely the three largest numbers in the array. This can be found in a single scan of the entire array.
Algorithm:
(*) Initialize m1, m2, m3 to zero.
(*) Loop through the entire array:
(*) set m to be max(arr[i], m1) (where arr[i] is the current element in the array).
(*) if m != m1, then m must be bigger. So set m3=m2, m2=m1, and m1 = m
(*) else m = max(m2, arr[i])
(*) if m != m2 (m must be bigger than m2). So set m3=m2, m2 = m
(*) else m3 = max(arr[i], m3)
The above algorithm is guaranteed to yield the three largest numbers in a single scan. This means storage is O(4), and time complexity is O(n).
Here is the algorithm:
#include <algorithm>
#include <iostream>
using namespace std;
void fs(int *arr, int size) {
int m, m1=0,m2=0,m3=0;
for (int i=0; i < size; i++) {
m = max(m1, arr[i]);
if (m != m1) {
m3=m2;
m2=m1;
m1=m;
} else {
m = max(m2, arr[i]);
if (m != m2) {
m3=m2;
m2 = m;
} else m3 = max(m3, arr[i]);
}
}
cout << m3 <<" "<<m2<<" "<<m1<<endl;
}
int main() {
int test[8] = {6,9,8,1,2,3,4,10};
fs(test, 8);
return 0;
}
I think this is possible in O(n), possible there are solutions already posted too..
Here is the logic (java biased).
1. Keep a result object with max, second_max, and third_max numbers.
2. Run through the array and record maximums, If you find a bigger value than max, push max to second_max, second_max to third_max and so on, until you have values in all. When you have values in all this is a possible result for you. Calculate the product and store the result. (result1)
3. Run through the rest of the array with a new result object.(result2). For any number greater than max in result1, recalculate result1 and clear result2. For any number less than third_max in result1, ignore. But for any number greater than result1.third_max, track it in result2, since we have a possibility of getting a better trio than result1.
4. If we get a better trio replace result2 with result1.
Time complexity is O(n). Space complexity is constant O(1)
One more addition.
When capturing result into result2, for any number greater than result.third_max, then new number will be result2.second_max, and result2.third_max will be same as result1.third_max. result2.max will be unassigned for now. Then you get another number greater than result.max, then you apply this to both result1 and result2 and then, decide which will prevail.
Here's an O(n^2) solution:
Find out all the increasing subsequences and for each subsequence greater than or equal to length three, find the product of the last three elements of the sequence.
int maxProd(vector<int> & v)
{
vector<int> length(v.size(), 1);
vector<int> prev(v.size(), -1);
for(size_t i = 0; i < v.size(); ++i)
{
for(size_t j = 0; j < i; ++j)
{
if(v[j] < v[i] && length[i] <= length[j])
{
prev[i] = j;
length[i] = length[j] + 1;
}
}
}
for(size_t i = 0; i < v.size(); ++i)
{
cout << i << " " << v[i] << " " << prev[i] << " " << length[i] << endl;
}
int maximum = 0;
for(size_t i = 2; i < length.size(); ++i)
{
if(length[i] >= 3)
{
int j(0), prod(v[i]), p(prev[i]);
while(j < 3)
{
prod *= v[p];
++j;
p = prev[p];
}
if(prod > maximum)
maximum = prod;
}
}
return maximum;
}
for each element a[i],we need to find
1.largest elemnt smaller than current element from 0 to i-1..will be stored in an array.
2. largest element greater than current element from i+1 to n-will be stored in oder array,
1. for finding first,we'll create a balanced BST or AVL and find floor.
insert a[0] in AVL tree
start loop from i=1 to i=n-2
search for floor in AVL and store in another array say b
insert a[i] in AVL
2. for second array,linear scan.(finding greatest element on right side).
and store this value for each element in a diff array say c
now check for every element
3.Now find index i for max a[i]*b[i]*c[i]
Time complexity--o(nlogn) for part 1 and o(n) for part 2 and 3..overall-o(nlogn)
space complexity-o(n)
So if I understand this correctly, the subsequence of 3 items has to be in ascending order and we must find the subsequence of 3 items which are in ascending order which has the largest product.
This is achievable in O(N) time and with no additional storage other than a few local ints (mostly there for clarity). Basically, you walk the array, testing three sequential elements at a time. If they are ascending, then they are eligible to have the highest product. Each time you find a valid ascending subsequence that has a higher product, store the index that it was found for later retrieval and store what that product was for future testing.
public class GeneralQuestions
{
private static final int LEFT_OFFSET = 2;
private static final int MIDDLE_OFFSET = 1;
/**
* Find a subsequence of size 3 that produces the largest
* product. The subsequence must be in ascending order.
*/
public int[] findMaxProductFromArray(final int[] inputArray)
{
// Always start at index 2 (3rd element)
int currentRightIdx = LEFT_OFFSET;
// Storage when we find a valid subsequence with the highest product
int bestRightIdx = -1;
// Storage for the highest product found and the current product being tested
int highestProduct = 0, currentProduct = 0;
// These aren't functionally needed but provide clarity
int left, middle, right;
// Continue until we reach the end of the array
while (currentRightIdx < inputArray.length)
{
// Assign the current values for clarity sake
left = inputArray[currentRightIdx - LEFT_OFFSET];
middle = inputArray[currentRightIdx - MIDDLE_OFFSET];
right = inputArray[currentRightIdx];
// We have a valid subsequence if all three elements are in ascending order
if (left < middle && middle < right)
{
// If the product of this valid subsequence is greater than the
// previous one found, store the index location.
currentProduct =
calc(inputArray, currentRightIdx - LEFT_OFFSET, currentRightIdx);
if (currentProduct > highestProduct)
{
highestProduct = currentProduct;
bestRightIdx = currentRightIdx;
}
}
++currentRightIdx;
}
int[] results;
if (bestRightIdx > -1)
{
// For clarity, assign the highest product elements and return them
// all in an array (great for testing)
left = inputArray[bestRightIdx - LEFT_OFFSET];
middle = inputArray[bestRightIdx - MIDDLE_OFFSET];
right = inputArray[bestRightIdx];
results = new int[]{left, middle, right};
}
else
{
// No valid results
results = new int[]{};
}
return results;
}
/**
* General purpose calculator of products for an array for a given range.
* If we always assume 3 things, then we could obviously hard code that.
*/
private int calc(int[] arr, int lowIdx, int highIdx)
{
int result = 1;
for (int idx = lowIdx; idx <= highIdx; ++idx)
{
result = result * arr[idx];
}
return result;
}
}
We need to process the data from right to left and create a relationship tree in the following manner for 6 7 8 1 2 3 9 10.
If smaller than current chains smallest element, cost O(1)
1. 10
2. 10 9
3. 10 9 3
4. 10 9 3 2
5. 10 9 3 2 1
If greater than current chains smallest element, binary search cost O(log n)
6. 10 9 3 2 1
----------8
7. 10 9 3 2 1
----------8 7
7. 10 9 3 2 1
----------8 7 6
Now the answer is in one of the root to leaf paths, which can be found in O(n). So, total time O(n log n) and space O(n).
Solution in C++ with O(n) running time and O(n) space complexity:
#include <iostream>
#include <vector>
using namespace std;
void printSubSequence(vector<int> L) {
vector<int> L1(L.size());
vector<int> L2(L.size() - 1);
L1[L.size() - 1] = L[L.size() - 1];
for (int i = L.size() - 2; i >= 0; --i) {
L1[i] = (L[i] > L1[i + 1]) ? L[i] : L1[i + 1];
}
L2[L.size() - 2] = (L[L.size() - 2] <= L[L.size() - 1]) ? L[L.size() - 2] : -1;
for (int i = L.size() - 3; i >= 0; --i) {
L2[i] = (L[i] <= L1[i + 1] && L[i] * L1[i + 1] > L2[i + 1] * L1[i + 2]) ? L[i] : L2[i + 1];
}
int maxProd = -1, maxIdx;
for (int i = L.size() - 3; i >= 0; --i) {
if (L[i] <= L2[i + 1] && L[i] * L2[i + 1] * L1[i + 2] >= maxProd) {
maxIdx = i;
maxProd = L[i] * L2[i + 1] * L1[i + 2];
}
}
cout << L[maxIdx] << " " << L2[maxIdx + 1] << " " << L1[maxIdx + 2] << endl;
}
O(n) solution:
#include <iostream>
#include <climits>
#include <utility>
using namespace std;
int main() {
// your code goes here
int n, i;
cin>>n;
int arr[n];
for(i = 0; i<n; i++)
cin>>arr[i];
int max = INT_MIN, a = 0, b = 0, c = 0;
pair<int, int> max_pair = make_pair(INT_MIN, INT_MIN);
for(i = n-1; i>=0; i--) {
if(arr[i] <= max_pair.first) {
if(arr[i]*(max_pair.first)*(max_pair.second) > a*b*c) {
a = arr[i];
b = (max_pair.first);
c = (max_pair.second);
}
}
else if(arr[i] <= max) {
max_pair.first = arr[i];
max_pair.second = max;
}
else
max = arr[i];
}
cout<<a<<" "<<b<<" "<<c<<endl;
return 0;
}
O(n) solution: We maintain maximum and maximum pair(pair whose 1st element is maximum than any other pair)
On finding a new element, check if the subseq of length three can be formed. If not (happens when elem<pair.first) check if max pair can be formed by comparing (elem <= max). If not, it is the maximum element. So update max.
#include <iostream>
#include <climits>
#include <utility>
using namespace std;
int main() {
// your code goes here
int n, i;
cin>>n;
int arr[n];
for(i = 0; i<n; i++)
cin>>arr[i];
int max = INT_MIN, a = 0, b = 0, c = 0;
pair<int, int> max_pair = make_pair(INT_MIN, INT_MIN);
for(i = n-1; i>=0; i--) {
if(arr[i] <= max_pair.first) {
if(arr[i]*(max_pair.first)*(max_pair.second) > a*b*c) {
a = arr[i];
b = (max_pair.first);
c = (max_pair.second);
}
}
else if(arr[i] <= max) {
max_pair.first = arr[i];
max_pair.second = max;
}
else
max = arr[i];
}
cout<<a<<" "<<b<<" "<<c<<endl;
return 0;
}
//Working solution, works for any triplet problem
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] arr = {6,7,8,1,2,3,9,10};
findSub(arr);
}
public static void findSub(int[] arr){
int max = 0;
for(int i=0;i<arr.length;i++){
int left = i+1;
int right = arr.length-1;
while(left<right){
if(arr[i] * arr[left] * arr[right] > max){
max = (arr[i] * arr[left] * arr[right]);
System.out.println(arr[i] + "," + arr[left] + "," + arr[right] + " = " + max);
break;
}
else if(arr[i] * arr[left] * arr[right] < max){
left++;
}
else{
right--;
}
}
}
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] arr = {6,7,8,1,2,3,9,10};
findSub(arr);
}
public static void findSub(int[] arr){
int max = 0;
for(int i=0;i<arr.length;i++){
int left = i+1;
int right = arr.length-1;
while(left<right){
if(arr[i] * arr[left] * arr[right] > max){
max = (arr[i] * arr[left] * arr[right]);
System.out.println(arr[i] + "," + arr[left] + "," + arr[right] + " = " + max);
break;
}
else if(arr[i] * arr[left] * arr[right] < max){
left++;
}
else{
right--;
}
}
}
}
}
Why don't we just keep a queue of length 3, the queue can be kept automatically sorted by inserting a new number only if it is larger than the top item in queue.
Just iterate thru given array. All 3 first items 6,7,8 will be in queue in given example. But when 9 comes, 6 will fall off, we have 7,8,9.
When 10 comes, we get what'd be final result - 8,9,10.
Since we're dealing w/ non-neg numbers, just multiply largest 3 numbers 8.9.10 and that's the answer 720 -- for the given example.
java function:
public void findMaxSequence(int[] arr, int n) {
int maxIndex = -1;
int maxSum = 0;
if (n < 3) return;
int i = 0;
while ( i < (n-2)) {
if (arr[i] > arr[i+1] || arr[i+1] > arr[i+2]) {
i++;
continue;
}
if (arr[i] + arr[i+1] + arr[i+2] > maxSum) {
maxSum = arr[i] + arr[i+1] + arr[i+2];
maxIndex = i; i++;
}
}
if (maxIndex != -1 )
System.out.printf("Max Sub string: %d,%d,%d",arr[maxIndex],arr[maxIndex + 1], arr[maxIndex +2]);
}
I think,this is O(n). Any suggestion / input will be helpful
int sequence[]=new int[]{6,7,8,1,2,3,9,10};
int maxSum=0;
for(int i=0;i<sequence.length-2;i++){
if(maxSum<sequence[i]+sequence[i+1]+sequence[i+2]){
maxSum=sequence[i]+sequence[i+1]+sequence[i+2];
firstMax=sequence[i];
secondMax=sequence[i+1];
thirdMax=sequence[i+2];
}
System.out.println(firstMax+"*"+secondMax+"*"+thirdMax+" = "+firstMax*secondMax*thirdMax);
public static void maximumAscendingSequenceBoundary(int[] data)
{
for (int i = 0; i < data.length; i++) {
int lowerbound = i;
int middle = 0;
int upperbound = i;
int numberOfIntermediates = 0;
// find the upperbound of data[i]
for (int j = i+1; j < data.length; j++) {
if (data[i] < data[j] && data[j] > data[upperbound]) {
upperbound = j;
}
}
// if no upperbound is found then continue to the next lowerbound candidate
if (upperbound == 0) {
continue;
}
// if you find two better candidates between the lower and upper bound, cont
for (int j = i+1; j < upperbound; j++) {
if (data[j] > data[lowerbound] && data[j] < data[upperbound]) {
middle = j;
numberOfIntermediates++;
}
}
// if there is only one candidate between the lower and upper bound
if (numberOfIntermediates == 1) {
System.out.println(data[lowerbound] + ", " + data[middle] + ", " + data[upperbound]);
break;
}
}
}
- techpanja November 15, 2013public static int[] findSubsequenceWithMaxProduct(int[] inputArray) { int maxProduct = 0; int[] subsequenceWithLargestProduct = new int[3]; for (int i = 1; i < inputArray.length - 1; i++) { int leftLowest = 0; int rightHighest = 0; // find lowest on the left. for (int j = 0; j < i; j++) { if (inputArray[j] < inputArray[i] && inputArray[j] > leftLowest) { leftLowest = inputArray[j]; } } // find highest on right. for (int k = i + 1; k < inputArray.length; k++) { if (inputArray[k] > inputArray[i] && inputArray[k] > rightHighest) { rightHighest = inputArray[k]; } } int currentProduct = inputArray[i] * leftLowest * rightHighest; if (currentProduct > maxProduct) { maxProduct = currentProduct; subsequenceWithLargestProduct = new int[]{leftLowest, inputArray[i], rightHighest}; } } return subsequenceWithLargestProduct; }