## Facebook Interview Question

Software Engineers**Country:**United States

Assumptions:

- add a single {+,-,*,/} between two numbers forming an algebraic expression that should be maximized: (n-1) choices

- *,/ takes precedence over +,-

- the order in which the numbers occur is given by the array, no re-ordering

- positive and negative numbers occur

Solution:

First, I just write down the recursion, by assumeing x/0 as not defined and

thus not valid in integer space (one could also argue x/0 = + infinite...)

```
rec(prod, i) =
max [
prod + rec(array[i], i + 1),
prod - rec(array[i], i + 1),
rec(prod * array[i], i + 1),
rec(prod / array[i], i + 1), if array[i] != 0, can help
] if i < n
prod if i = n
```

this will do it... it's exponential: O(4^n).

Greedy choice won't help because e.g.:

-5 * 5 * 5 * -1 > -5 + 5 + 5 + -1

but

-5 * 5 < -5 + 5

etc...

or

2 * 1 * 4 > 2 + 1 + 4

but

2 * 1 * 2 < 2 + 1 + 2

etc...

now one can go and chase down cases where fewer

choices will do it in the recursion. For example, it's not right away

obvious when division helps at all and there might cases one doesn't

need to explore the division part of the branch.

the recursion has two arguments, so, I'd create a table like the one

below and further analyze...

```
case |prod | array[i] | {operations}, comment
----------------------------------------------------------
1.a |= 0 | = 0 | {+}, doesn't matter, + will do it
b | | = 1 | {+,-}, +: e.g. 0+1*8, -: e.g. 0-1*-8
c | | = -1 | {+,-}, see above
d | | > 1 | {+,-}, see above
e | | < -1 | {+,-}, see above
----------------------------------------------------------
2.a |= 1 | = 0 | {+}, (see case 1.a)
b | | = 1 | {+,-}, +: e.g. 1+1*8, -: e.g. 1-1*-8
c | | = -1 | {+,-}, see above
d | | > 1 | {+,-}, see above
e | | < -1 | {+,-}, see above
----------------------------------------------------------
3.a |= -1 | = 0 | {+} (see case 1.a)
b | | = 1 | etc.
c | | = -1 | ..
d | | > 1 |
e | | < -1 |
----------------------------------------------------------
4.a |> 1 | = 0 |
b | | = 1 |
c | | = -1 |
d | | > 1 |
e | | < -1 |
----------------------------------------------------------
5.a |< -1 | = 0 |
b | | = 1 |
c | | = -1 |
d | | > 1 |
e | | < -1 |
```

there are many cases, not sure this leads to an elegant solution. How ever

one would figure out if '/' is useful at all...

or, when I was more familiar with existing NP complete and NP hard problems

I would start a discussion to prove the thing is NP complete or NP hard.

or I would ask for a hint, but I'm quite not sure it exists

or I'd start to add constraints, like no 0, no negative numbers, no 1s etc... to

simplify the problem

anyway, here the exponential, recursive version in python 3 with an incomplete

list of tests.

```
def max_number(arr):
def sub_problem(prod, i):
if i == len(arr):
return prod
c = max(prod + sub_problem(arr[i], i + 1), prod - sub_problem(arr[i], i + 1), sub_problem(prod * arr[i], i + 1))
if arr[i] != 0:
return max(c, sub_problem(prod / arr[i], i + 1))
else:
return c
return sub_problem(0, 0)
print(max_number([2,1,1,1])) #2+1+1+1 = 5
print(max_number([2,1,1,1,9])) # 2*1*1*1*9 = 18
print(max_number([2,1,-2])) #2+1--2 = 5
print(max_number([2,0,2])) # 2+0+2 = 4
print(max_number([-5,1,1,1,1,-3])) # 15
```

Hey @ChrisK,

I would assume that you can't put a "-" before that first element.

If given the array [-1,2,3], your code produces the value 6, implying that the code added a "-" before the first "-1" and then multiplied it with 2 and 3.

I would just start the sub_problem function from the first element to begin with.

```
def max_number2(arr):
def sub_problem(prod, i):
if i == len(arr):
return prod
c = max(prod + sub_problem(arr[i], i + 1), prod - sub_problem(arr[i], i + 1), sub_problem(prod * arr[i], i + 1))
if arr[i] != 0:
return max(c, sub_problem(prod / arr[i], i + 1))
else:
return c
return sub_problem(arr[0], 1)
```

I am assuming, the question meant use +-*/ among the numbers in the array and return the max number.

Case1: if number > 1 multiply

Case 2: If number ==1 or number ==0, add

Case 3: if number < 0, multiply the negative numbers and see the final outcome is negative or positive, If negative divide the last number and subtract it to get the maximum number. if positive, that is the maximum number.

Let me know if my solution is correct.

private static int maxNumber(int[] nums) {

if(nums.length == 0) return 0;

Arrays.sort(nums);

int maxNumber = nums[nums.length - 1];

boolean containsNegative = false;

for(int i = nums.length -2; i >=0; i--){

if(nums[i] > 1) maxNumber *= nums[i];

else if(nums[i] == 0 || nums[i] == 1) maxNumber += nums[i];

else

{

containsNegative = true;

break;

}

}

if(containsNegative) {

int i = 0;

int negativeNum = nums[0];

while (nums[i] < 0) {

maxNumber *= nums[i];

negativeNum = nums[i];

i++;

}

if(maxNumber < 0){

maxNumber /= negativeNum;

maxNumber -= negativeNum;

}

}

return maxNumber;

}

```
int[] arr = {-4, -3, -2, -1, 1, 1, 2, 3};
int[] newarr = new int[arr.length];
int j = 0, i = 0;
for (i = 0; i < arr.length - 2; i++) {
if (arr[i] < 0 && arr[i + 1] < 0) {
newarr[j++] = arr[i] * arr[i + 1];
i++;
} else {
newarr[j++] = arr[i];
}
}
while (i < arr.length) {
newarr[j++] = arr[i++];
}
System.out.println("ans: new: " + Arrays.toString(newarr));
Arrays.sort(newarr);
int leftover = 0, startIndex = 0,count_ones=0;
int k = 0;
for (int q = 0; q < newarr.length; q++) {
if (newarr[q] <= 0) {
startIndex++;
leftover += newarr[q];
}
if (newarr[q]==1){
count_ones++;
}
}
System.out.println("ans: startIndex: " + startIndex+" |left="+leftover+" |count_ones="+count_ones);
int[] input = new int[newarr.length - startIndex-count_ones];
System.arraycopy(newarr, startIndex+count_ones, input, 0, newarr.length - startIndex-count_ones);
System.out.println("ans: input: " + Arrays.toString(input));
//int maxsum= findsum(arr,0,arr[0]);
while(count_ones!=0){
input[0]+=1;
Arrays.sort(input);
count_ones--;
}
System.out.println("ans: new input: " + Arrays.toString(input));
int ans=input[0];
for(int m = 1;m<input.length;m++){
ans*=input[m];
}
ans-=leftover;
System.out.println("ans:"+ans);
```

Assuming it has no zero, if it has zero, remove zeroes in O(n). Should be simple to implement.

```
int[] arr = {-4, -3, -2, -1, 1, 1, 2, 3};
int[] newarr = new int[arr.length];
int j = 0, i = 0;
for (i = 0; i < arr.length - 2; i++) {
if (arr[i] < 0 && arr[i + 1] < 0) {
newarr[j++] = arr[i] * arr[i + 1];
i++;
} else {
newarr[j++] = arr[i];
}
}
while (i < arr.length) {
newarr[j++] = arr[i++];
}
System.out.println("ans: new: " + Arrays.toString(newarr));
Arrays.sort(newarr);
int leftover = 0, startIndex = 0,count_ones=0;
int k = 0;
for (int q = 0; q < newarr.length; q++) {
if (newarr[q] <= 0) {
startIndex++;
leftover += newarr[q];
}
if (newarr[q]==1){
count_ones++;
}
}
System.out.println("ans: startIndex: " + startIndex+" |left="+leftover+" |count_ones="+count_ones);
int[] input = new int[newarr.length - startIndex-count_ones];
System.arraycopy(newarr, startIndex+count_ones, input, 0, newarr.length - startIndex-count_ones);
System.out.println("ans: input: " + Arrays.toString(input));
//int maxsum= findsum(arr,0,arr[0]);
while(count_ones!=0){
input[0]+=1;
Arrays.sort(input);
count_ones--;
}
System.out.println("ans: new input: " + Arrays.toString(input));
int ans=input[0];
for(int m = 1;m<input.length;m++){
ans*=input[m];
}
ans-=leftover;
System.out.println("ans:"+ans);
```

Hey ChrisK,

I would assume that you can't add a "-" before the first element.

Under that assumption, for the array [-1,2,3], your code would return 6 (-(-1)*2*3), while I would expect it to return 5 (-1+(2*3)).

I would add a simple modification to the code, starting the sub problem method on the first element of the array.

- lizka.k July 16, 2017