Skip to content

Instantly share code, notes, and snippets.

@randyhbh
Created December 19, 2018 01:13
Show Gist options
  • Select an option

  • Save randyhbh/38f8fa09d39e6465ffca6025df595397 to your computer and use it in GitHub Desktop.

Select an option

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
Copy Markdown
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