## Facebook Interview Question

Software Developers**Country:**United States

I thought same at first but I guess they are considering array from position 1 so the case will be L-1 and R-1.

(I guessed that from the test case given)

This is very good exercise to learn about segment trees.

once you build segment tree, for each query, do following;

L = query(0, l-1), M = query(l, r), R = query(r+1, n-1);

since the subarray between 'l' & 'r' is being reversed, all you got to do is swap, prefix and suffix sum for M.

answer will be L + M + R.

Here's an improved version of the question along with the answer in PHP :

```
//You are given an array A of size N and Q queries.
//For each query, you are given two indices of the array L and R.
//The subarray generated from L to R is reversed.
//Your task is to determine the maximum contiguous sum of the subarrays.
//Ex :
//5 2
//3 -1 4 2 -1
//3 4
//1 2
//Given array is {3,-1,4,2,-1}.
//For first query L=3 and R=4. Now the array becomes {3,-1,2,4,-1}.
//Maximum sub-array sum is 8 and the sub-array is {3,-1,2,4}.
//For second query L=1 and R=2. Now the array becomes {-1,3,4,2,-1}.
//Maximum sub-array sum is 9 and the sub-array is {3,4,2}.
function maxSubArray($array,$startTrans,$endTrans){
$newArray=array();
for($i=0;$i<sizeof($array);$i++){
if($i == $startTrans-1){
for($j=$endTrans-1;$j>=$i;$j--)
$newArray[]=$array[$j];
$i=$endTrans-1;
}else{
$newArray[]=$array[$i];
}
}
$max=0;$start=0;$end=0;$sum=0;
for($i=0;$i<sizeof($newArray);$i++){
$sum+=$newArray[$i];
if($sum>$max){
$max=$sum;
$end=$i;
}
if($sum<0){
$sum=0;
$start=$i+1;
}
}
return $max;
}
```

The output seems to be wrong I guess

- Anonymous October 29, 2018After first transformation , we get (3,-1,4,-1,2) , the output is 7

After second transformation , we get (3,4,-1,2,-1) , the output is 8

We can use Kadane's algorithm to find the max sum subarray