[finding the] maximum element in the array that would result from performing all M operationsHere’s the question by John that was looking for a Java solution:

With an array of N elements which are initialized to 0. we are given a sequence of M operations of the sortInteresting. Indeed, a naive solution would just perform all the operations as requested. Another naive but less naive solution would transform the operations into signals of the form`(p; q; r)`

. The operation`(p; q; r)`

signifies that the integer r should be added to all array elements`A[p];A[p + 1]; : : : ;A[q]`

. You are to output the maximum element in the array that would result from performing all M operations. There is a naive solution that simply performs all operations and then returns the maximum value, that takes`O(MN)`

time. We are looking for a more efficient algorithm.

`(x; y)`

for all `(p; r)`

and for all `(q + 1; -r)`

. In other words, we could implement the solution I had presented trivially as such:
```
// This is just a utility class to model the ops
class Operation {
final int p;
final int q;
final int r;
Operation(int p, int q, int r) {
this.p = p;
this.q = q;
this.r = r;
}
}
// These are some example ops
Operation[] ops = {
new Operation(4, 12, 2),
new Operation(2, 8, 3),
new Operation(6, 7, 1),
new Operation(3, 7, 2)
};
// Here, we're calculating the min and max
// values for the combined values of p and q
IntSummaryStatistics stats = Stream
.of(ops)
.flatMapToInt(op -> IntStream.of(op.p, op.q))
.summaryStatistics();
// Create an array for all the required elements using
// the min value as "offset"
int[] array = new int[stats.getMax() - stats.getMin()];
// Put +r and -r "signals" into the array for each op
for (Operation op : ops) {
int lo = op.p - stats.getMin();
int hi = op.q + 1 - stats.getMin();
if (lo >= 0)
array[lo] = array[lo] + op.r;
if (hi < array.length)
array[hi] = array[hi] - op.r;
}
// Now, calculate the prefix sum sequentially in a
// trivial loop
int maxIndex = Integer.MIN_VALUE;
int maxR = Integer.MIN_VALUE;
int r = 0;
for (int i = 0; i < array.length; i++) {
r = r + array[i];
System.out.println((i + stats.getMin()) + ":" + r);
if (r > maxR) {
maxIndex = i + stats.getMin();
maxR = r;
}
}
System.out.println("---");
System.out.println(maxIndex + ":" + maxR);
```

2:3 3:5 4:7 5:7 6:8 7:8 8:5 9:2 10:2 11:2 --- 6:8So, the maximum value is generated at position 6, and the value is 8.

## Faster calculation in Java 8

This can be calculated faster using Java 8’s new Arrays.parallelPrefix() operation. Instead of the loop in the end, just write:```
Arrays.parallelPrefix(array, Integer::sum);
System.out.println(
Arrays.stream(array).parallel().max());
```

`O(M+N)`

solution. Read up about prefix sums here.
## Now show me the promised SQL code

In SQL, the naive sequential and linear complexity solution can easily be re-implemented, and I’m showing a solution for PostgreSQL. How can we do it? We’re using a couple of features here. First off, we’re using common table expressions (also known as the`WITH`

clause). We’re using these to declare table variables. The first variable is the `op`

table, which contains our operation instructions, like in Java:
```
WITH
op (p, q, r) AS (
VALUES
(4, 12, 2),
(2, 8, 3),
(6, 7, 1),
(3, 7, 2)
),
...
```

`+r`

signal at all `p`

positions, and a `-r`

signal at all `q + 1`

positions:
```
WITH
...,
signal(x, r) AS (
SELECT p, r
FROM op
UNION ALL
SELECT q + 1, -r
FROM op
)
...
```

```
SELECT * FROM signal ORDER BY x
```

x r ------ 2 3 3 2 4 2 6 1 8 -2 8 -1 9 -3 13 -2All we need to do now is calculate a running total (which is essentially the same as a prefix sum) as follows:

```
SELECT x, SUM(r) OVER (ORDER BY x)
FROM signal
ORDER BY x
```

x r ------ 2 3 3 5 4 7 6 8 8 5 8 5 9 2 13 0Now just find the max value for

`r`

, and we’re all set. We’ll take the shortcut by using `ORDER BY`

and `LIMIT`

:
```
SELECT x, SUM(r) OVER (ORDER BY x) AS s
FROM signal
ORDER BY s DESC
LIMIT 1
```

x r ------ 6 8Perfect! Here’s the full query:

```
WITH
op (p, q, r) AS (
VALUES
(4, 12, 2),
(2, 8, 3),
(6, 7, 1),
(3, 7, 2)
),
signal(x, r) AS (
SELECT p, r
FROM op
UNION ALL
SELECT q + 1, -r
FROM op
)
SELECT x, SUM(r) OVER (ORDER BY x) AS s
FROM signal
ORDER BY s DESC
LIMIT 1
```