Today, I got a chance to come across a pretty elegant solution, involving 1) calculating difference array and 2) find ongoing prefix sum, in order to solve one problem from hackerrank.com

First, here comes the problem.

/* You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a, b and k and you have to add value k to all the elements ranging from index a to b(both inclusive). Input Format First line will contain two integers N and M separated by a single space. Next M lines will contain three integers a, b and k separated by a single space. Numbers in list are numbered from 1 to N. Output Format A single line containing maximum value in the updated list. Constraints 3<=N<=10^7 1<=M<=2*10^5 1<=a<=b<=N 0<=k<=10^9 Sample Input #00 5 3 1 2 100 2 5 100 3 4 100 Sample Output #00 200 Explanation After first update list will be 100 100 0 0 0. After second update list will be 100 200 100 100 100. After third update list will be 100 200 200 200 100. So the required answer will be 200. */

Speaking as an average level programmer, he/she or I could naturally start from a nested loop to read each input line and update each element in the array, and calculate the carrying max. Therefore, it cost O(N * T). But after I solve this "easy" problem, I just feel it could/should be improved to linear complexity somehow. I will talk this later.

*(N is array size, T is total test count #) *

Let's

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] arr = new long[n+1]; int t = sc.nextInt(); int a, b; long val; long max = 0l; for (int i = 0; i < t; i++) { a = sc.nextInt(); b = sc.nextInt(); val = sc.nextLong(); arr[a] += val; if((b+1)<=n) arr[b+1]-= val; } long x = 0l; for (int i = 0; i <= n ; i++) { x += arr[i]; max = Math.max(max, x); } System.out.println(max); }

Here comes the greater part to improve time complexity to O(M + N)

1) Use difference array.

2) Find max of all prefix sum.

For this problem, I would employ a max prefix sum scan on a difference array. To generate a set of range differences, we adjust arr[a] += val and arr[b+1] −= val. Going back to your sample data, your difference array would look like this:

To calculate the max prefix sum, accumulate the difference array to NN while taking the maximum accumulated prefix. (*) denotes new max found.

Building a difference array in O(M)O(M) and finding the max prefix sum in O(N)O(N) results in a O(M+N)O(M+N) linear algorithm.

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] arr = new long[n+1]; int t = sc.nextInt(); int a, b; long val; long max = 0l; for (int i = 0; i < t; i++) { a = sc.nextInt(); b = sc.nextInt(); val = sc.nextLong(); arr[a] += val; if((b+1)<=n) arr[b+1]-= val; } long x = 0l; for (int i = 0; i <= n ; i++) { x += arr[i]; max = Math.max(max, x); } System.out.println(max); }

In conclusion, I can imagine the most possible practical usage in trading could be applying same parameter addition to back test or optimize final output or just to control overhead of each parameter.