fork(10) download
copy 
  1. import java.util.Arrays;
  2. import java.util.PriorityQueue;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         int[] array = {1, 2, 1, 3, 1000};
  8.         System.out.println(Arrays.toString(findSums(array, 3)));
  9.     }
  10.  
  11.     private static long[] findSums(int[] array, int k) {
  12.         long maxSum = Arrays.stream(array).filter(it -> it >= 0).sum();
  13.  
  14.         int[] positives = Arrays.stream(array).filter(it -> it >= 0).sorted().toArray();
  15.         int[] negatives = Arrays.stream(array).filter(it -> it < 0).sorted().toArray();
  16.         // sort time complexity is O(n*log(n))
  17.  
  18.         PriorityQueue<Long> sums = new PriorityQueue<>(k); // priority queue is implemented using heap so adding element has time complexity O(log(n))
  19.         sums.add(maxSum); // we start with max sum - combination of all positive elements
  20.  
  21.         int previous = Integer.MIN_VALUE;
  22.         Long[] previousAddedSums = {};
  23.         Long[] sumsToIterate;
  24.  
  25.         // iterate over positive values
  26.         for (int i = 0; i < positives.length; i++) {
  27.             if (positives[i] == previous) {
  28.                 sumsToIterate = previousAddedSums;
  29.             } else {
  30.                 sumsToIterate = sums.toArray(new Long[sums.size()]);
  31.             }
  32.             previousAddedSums = new Long[sumsToIterate.length];
  33.             for (int j = 0; j < sumsToIterate.length; j++) {
  34.                 long newSum = sumsToIterate[j] - positives[i];
  35.                 // new sum is calculated - value positives[i] is removed from combination (subtracted from sum of that combination)
  36.                 sums.add(newSum);
  37.                 previousAddedSums[j] = newSum;
  38.                 if (sums.size() > k) {
  39.                     sums.poll(); // only first k maximum sums are needed at the moment
  40.                 }
  41.             }
  42.             previous = positives[i];
  43.         }
  44.  
  45.         previous = Integer.MAX_VALUE;
  46.         // iterate over negative values in reverse order
  47.         for (int i = negatives.length - 1; i >= 0; i--) {
  48.             if (negatives[i] == previous) {
  49.                 sumsToIterate = previousAddedSums;
  50.             } else {
  51.                 sumsToIterate = sums.toArray(new Long[sums.size()]);
  52.             }
  53.             previousAddedSums = new Long[sumsToIterate.length];
  54.             for (int j = 0; j < sumsToIterate.length; j++) {
  55.                 long newSum = sumsToIterate[j] + negatives[i]; // value negatives[i] is added to combination (added to sum of that combination)
  56.                 sums.add(newSum);
  57.                 previousAddedSums[j] = newSum;
  58.                 if (sums.size() > k) {
  59.                     sums.poll();
  60.                 }
  61.             }
  62.             previous = negatives[i];
  63.         }
  64.  
  65.         long[] result = new long[sums.size()];
  66.         for (int i = sums.size() - 1; i >=0 ; i--) {
  67.             result[i] = sums.poll();
  68.         }
  69.         // get sums from priority queue in proper order
  70.         return result;
  71.  
  72.         // this whole method has time complexity O(n * k * log(k))
  73.         // k is less than or equal 2000 so it should be good enough ;)
  74.     }
  75.  
  76. }
  77.  
Success #stdin #stdout 0.08s 50708KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[1007, 1006, 1005]
https://ideone.com/yf6POI
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!