Does this affect the time complexity? Can I improve it?

Discussion in 'Programming' started by LagBug, Mar 6, 2020.

  1. Hey there, I am participating in a competition and we are asked to create an algorithm which after reading a set of numbers, will find the 2 max and contiguous sets of 3 (or any other number) numbers. When two numbers meet for two profits, the number is not doubled.The algorithm which I've come up with is this:
    Code (Java):
    for (int i = 0; i < shops.length; i++) {
        int[] firstSet = shops[i];
        int c = 1;
        log("Starting #" + i + " with " + getIntArrayToString(firstSet));

        for (int j = i + 1; j < shops.length; j++) {
            int[] secondSet = shops[j];
            log(" Comparing with " + getIntArrayToString(secondSet));
            int currentSum = findSum(firstSet, secondSet);
            if (c <= contiguousShops) {
                for (int g = c; g < firstSet.length; g++) {
                    log("   Removed " + firstSet[g] + " as a duplicate");
                    currentSum -= firstSet[g];
                }
            }
            c++;
            if (currentSum > sum) {
                sum = currentSum;
                log("Current sum is " + sum);
            }
        }
    }
    My question is, since I have the if statement if (c <= contiguousShops) { will the loop inside it count when analyzing the time complexity? Would it be O(n^2) or O(n^3)?
    Also, what would be a good way to optimize/change this algorithm for better time complexity? I am not looking for the code, just for some guidance on the logic.

    e.x.
    Set of numbers: "1 5 20 20 20 15 10 1 1 1"
    Max: 5+20+20 plus 20+15+10 = 90
     
  2. Yeah, it would be O(n^3) because the big O means the worst case scenario. In this case, having that boolean expression evaluate to true is the worse case.
     
  3. Thanks for the reply. That makes things clearer. Do you (or anyone else) have any suggestions about my second question?
     
  4. If I understand the problem correctly, you have an array of integers and you need to find 3 numbers inside that array that are next to each other, find the sum of that, then find another 3 numbers that are after the previous 3 numbers, sum those as well and the sum of those sums should be as large as possible? If that's the case, that sounds like something that can at least be done in O(n^2). An outer loop for the first three numbers and another for the second three numbers. The outer loop goes from 0 to n - 3 in the array and the inner one goes from the position of the outer loop + 1 up to n - 3 in the array. Sum the numbers in the outer loop and in the inner loop, check against the previous maximum sum and replace if needed.
     
  5. There's a few O(n) algorithms. To get from @Stef's approach to one of these, try to make use of the fact that you essentially have two cases; either the two resulting sets touch each other, or they don't. If they touch each other, great, you just need a contiguous set of 6. If they don't, great, just search for the largest set of 3, then the second largest set of 3. If you try both, and take whichever gave you a larger sum, you got the result.

    Detailed explanation: First, we'll need an algorithm to find the single (instead of two) max contiguous set of 3 (or whatever) elements. You can do this by iterating through all elements starting from the third one, and keeping a variable which has the sum of the last three elements (initialize it with shops[0]+shops[1]+shops[2], then on every loop iteration remove shops[i-3] and add shops[ i]. Alternatively, for a O(3n)=O(n) solution, you can also just sum the last three elements in every iteration, which is fine for 3 but slow if the set size is larger). Now, on each iteration, compare the current sum of the last 3 elements with the "highscore", if its greater, update the highscore.

    Now, that algorithm only finds one set. The idea is as follows: We can just run our algorithm once for a set, remove the first set from the lost of shops, and run it again to get the second set. This might sound obvious but it's not as straightforward as you might think; look at this special case:
    0 0 3 5 5 5 3 1 0
    The first iteration of our algorithm will return [5,5,5]. However, we see that the best solution is the sets [3,5,5] and [5,3,1], and neither are [5,5,5]! That's where the "remove elements" trick comes in. By removing [5,5,5], we get the following numbers:
    0 0 3 3 1 0
    And here the largest set is [3,3,1]! Together, these two sets form one contiguous set of 6 numbers, and it's the same one formed by [3,5,5] [5,3,1], but [3,3,1] is not contiguous in the original array. You'll have to consider this special case in your algorithm and make sure you output [3,5,5] and [5,3,1] instead of [5,5,5] [3,3,1].

    Another O(n) solution uses dynamic programming (table size (n+1)*(2+1), maybe easier to find if you've heard of DP before.