Created
December 19, 2018 01:13
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You can check the problem description here