fork(1) download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. public int maxSumTwoNoOverlap(int[] A, int L, int M) {
  11.  
  12. // Construct prefix sum
  13. // This array contains sum of all contiguous elements
  14. for (int i = 1; i < A.length; i++) {
  15. A[i] = A[i - 1] + A[i];
  16. }
  17.  
  18. // Assign initial values so we can skip 1st run in below for loop
  19. // Taking the default result to be the first L + M elements
  20. int res = A[L + M - 1];
  21.  
  22. int maxL = A[L - 1];
  23. int maxM = A[M - 1];
  24.  
  25. // Either L before M or M before L, start this loop at index L + M
  26. for (int i = L + M; i < A.length; i++) {
  27.  
  28. // Keep track maxL so far
  29. // L before M: A[i - M] - A[i - M - L] is sum of L-length sub array
  30. maxL = Math.max(maxL, A[i - M] - A[i - M - L]);
  31.  
  32. // Keep track maxM so far
  33. // M before L: A[i - M] - A[i - L - M] is sum of M-length sub array
  34. maxM = Math.max(maxM, A[i - L] - A[i - L - M]);
  35.  
  36. // Keep track res so far
  37. // maxL + (A[i] - A[i - M]): Sum of max L-length sub array and current M-length sub array
  38. // maxM + (A[i] - A[i - L]): Sum of max M-length sub array and current L-length sub array
  39. res = Math.max(res, Math.max(maxL + (A[i] - A[i - M]), maxM + (A[i] - A[i - L])));
  40. }
  41.  
  42. return res;
  43. }
  44. public static void main (String[] args) throws java.lang.Exception
  45. {
  46. // your code goes here
  47. Ideone x = new Ideone();
  48. int[] A = {3, 8, 1, 3, 2, 1, 8, 9, 0};
  49. int L = 3;
  50. int M = 2;
  51. System.out.println(x.maxSumTwoNoOverlap(A, L, M));
  52. }
  53. }
Success #stdin #stdout 0.04s 2184192KB
stdin
Standard input is empty
stdout
29