write an algorithm to find the maximum value

Question

Example:
numbers are [1, 2, 3] and u have +, * max value is 1+2*3

example [1, 1, 1] , ans is 1+1+1

I can think of a simple recursive algorithm:

private static double helper(double[] arr, int s, int e) {
   System.out.println("s= " + s + " e= " + e);
   //base case:  if single elem, return that eleme
   if (e==s) {
      return arr[s];
    } if (s+1==e) {
        return Math.max(arr[s]+arr[e], arr[s]*arr[e]);
      } else if (s>e) {
      //this should never happen
      throw new UnsupportedOperationException("invalid operation");
   }

   //int mid = s+ ((e-s)/2);
   int mid=s;
    double fMax = Double.MIN_VALUE;
   for (mid=s;mid<e;mid++) {
     //divide and conqr route
     double lres = helperDQ(arr,s, mid);
     double  rres = helperDQ(arr,mid+1, e );
     System.out.println("s= " + s + " e = " + e + " m = " + mid + " lres= " + lres + " rres= " + rres);
     fMax = Math.max(fMax, Math.max(lres*rres, lres+rres));
    }
    return fMax;  
} 

private static double findMax(double[] arr) {
        return helper(arr, 0, arr.length-1);
}

Is there a better way to do instead of this recursive way? We can prune the recursion by checking for s, e so we dont end up recursing same thing multiple times.

Can't think of an easy dynamic programming approach way.

Any suggestions?

0 and 1 should always be added, any other value should be multiplied. You want to add 1 to the smallest number available. — Peter Lawrey
– Peter Lawrey, Commented Jul 23, 2015 at 4:36
It can be easily done using variant of chain matrix multiplication and i guess it has been answered on SO before many times — Shubham Sharma
– Shubham Sharma, Commented Jul 23, 2015 at 5:24

score 2 · Accepted Answer · 2015-07-23 15:14:53Z

2

This can actually be solved a lot easier, using some simple math. For any two numbers a and b, the following applies: unless either a = 1 or b = 1 is given, a * b >= a + b is given (assuming a >= 1 and b >= 1). This applies recursively to any set of numbers. Thus the maximum will always be achieved by

int maxNum(int[] nums){
    int x = 0;

    for(int n : nums)
        if(n == 1)
            x += n;
        else
            if(x == 0)
                x = n;
            else
                x *= n;
    return x;
}

If the set of numbers is order.

edited Jul 23, 2015 at 15:14

answered Jul 23, 2015 at 0:09

user4668606

Sign up to request clarification or add additional context in comments.

6 Comments

Gene Over a year ago

He didn't make it explicit, but the problem allows the numbers to be negative.

xXliolauXx Over a year ago

Yeah, but that really is too simple to be mentioned: if(n<0){if(x<0){x*=n}else{x+=n}. This does have a little flaw, where the algorithm is trying to make the number always positive, but a higher x could be achieved by multiplying with two negatives, but I think the performance improvement is worth that. +1 for the nice idea

xXliolauXx Over a year ago

@Paul there is a little mistake btw: if(n==1) you should add one, not multiply...

user4668606 Over a year ago

@xXliolauXx oops, little typo. thanks, ill correct it

user3282540 Over a year ago

i dont think it can be that easy Paul.. with your solution, if i give u 1, 2, 2 u'll return 4 or may be 5 but right answer would be 6 (1+2)*2 btw do you see any issue with my solution?

|

Collectives™ on Stack Overflow

write an algorithm to find the maximum value

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related