Skip to content

Instantly share code, notes, and snippets.

@randyhbh
Created December 19, 2018 01:13
Show Gist options
  • Save randyhbh/38f8fa09d39e6465ffca6025df595397 to your computer and use it in GitHub Desktop.
Save randyhbh/38f8fa09d39e6465ffca6025df595397 to your computer and use it in GitHub Desktop.
This solution applying array differences; Instead of storing the actual values in the array, you store the difference between the current element and the previous element.
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] queries = new int[m][3];
for (int i = 0; i < m; i++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int j = 0; j < 3; j++) {
int queriesItem = Integer.parseInt(queriesRowItems[j]);
queries[i][j] = queriesItem;
}
}
long result = arrayManipulation(n, queries);
System.out.println(result);
scanner.close();
}
static long arrayManipulation(int n, int[][] queries) {
long max = 0;
long[] arrayOperations = new long[n];
int j = 0;
for (int[] query : queries) {
int left = query[j];
int right = query[j + 1];
int operator = query[j + 2];
arrayOperations[left - 1] += operator;
if (right < n) arrayOperations[right] -= operator;
}
long temp = 0;
for (int i = 0; i < n; i++) {
temp += arrayOperations[i];
if (max < temp)
max = temp;
}
return max;
}
@randyhbh
Copy link
Author

You can check the problem description here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment