O(n^2) algorithm to find largest 3 integer arithmetic series

Question

The problem is fairly simple. Given an input of N (3 <= N <= 3000) integers, find the largest sum of a 3-integer arithmetic series in the sequence. Eg. (15, 8, 1) is a larger arithmetic series than (12, 7, 2) because 15 + 8 + 1 > 12 + 7 + 2. The integers apart of the largest arithmetic series do NOT have to be adjacent, and the order they appear in is irrelevant.

An example input would be:

6
1 6 11 2 7 12

where the first number is N (in this case, 6) and the second line is the sequence N integers long.

And the output would be the largest sum of any 3-integer arithmetic series. Like so:

21

because 2, 7 and 12 has the largest sum of any 3-integer arithmetic series in the sequence, and 2 + 7 + 12 = 21. It is also guaranteed that a 3-integer arithmetic series exists in the sequence.

EDIT: The numbers that make up the sum (output) have to be an arithmetic series (constant difference) that is 3 integers long. In the case of the sample input, (1 6 11) is a possible arithmetic series, but it is smaller than (2 7 12) because 2 + 7 + 12 > 1 + 6 + 11. Thus 21 would be outputted because it is larger.

Here is my attempt at solving this question in C++:

#include <bits/stdc++.h>
using namespace std;
vector<int> results;
vector<int> middle;
vector<int> diff;
int main(){
    int n;
    cin >> n;
    int sizes[n];
    for (int i = 0; i < n; i++){
        int size;
        cin >> size;
        sizes[i] = size;
    }
    sort(sizes, sizes + n, greater<int>());
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            int difference = sizes[i] - sizes[j];
            diff.insert(diff.end(), difference);
            middle.insert(middle.end(), sizes[j]);
        }
    }
    for (size_t i = 0; i < middle.size(); i++){
        int difference = middle[i] - diff[i];
        for (int j = 0; j < n; j++){
            if (sizes[j] == difference) results.insert(results.end(), middle[i]);
        }
    }
    int max = 0;
    for (size_t i = 0; i < results.size(); i++) {
        if (results[i] > max) max = results[i];
    }
    int answer = max * 3;
    cout << answer;
    return 0;
}

My approach was to record what the middle number and the difference was using separate vectors, then loop through the vectors and search if the middle number minus the difference is in the array, where it gets added to another vector. Then the largest middle number is found and multiplied by 3 to get the sum. This approach made my algorithm go from O(n^3) to roughly O(n^2). However, the algorithm doesn't always produce the correct output (and I can't think of a test case where this doesn't work) every time, and since I'm using separate vectors, I get a std::bad_alloc error for large N values because I am probably using too much memory. The time limit in this question is 1.4 sec per test case, and memory limit is 64 MB.

Since N can only be max 3000, O(n^2) is sufficient. So what is an optimal O(n^2) solution (or better) to this problem?

Answer 1

So, a simple solution for this problem is to put all elements into an std::map to count their frequencies, then iterate over the first and second element in the arithmetic progression, then search the map for the third.

Iterating takes O(n^2) and map lookups and find() generally takes O(logn).

include <iostream>
#include <map>
using namespace std;

const int maxn = 3000;
int a[maxn+1];
map<int, int> freq;

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {cin >> a[i]; freq[a[i]]++;} // inserting frequencies

    int maxi = INT_MIN;
    for (int i = 1; i <= n-1; i++)
    {
        for (int j = i+1; j <= n; j++)
        {
            int first = a[i], sec = a[j]; if (first > sec) {swap(first, sec);} //ensure that first is smaller than sec
            int gap = sec - first; //calculating difference
            if (gap == 0 && freq[first] >= 3) {maxi = max(maxi, first*3); } //if first = sec then calculate immidiately
            else
            {
                int third1 = first - gap; //else there're two options for the third element
                if (freq.find(third1) != freq.end() && gap != 0) {maxi = max(maxi, first + sec + third1); } //finding third element
            }
        }
    }
    cout << maxi;
}

Output : 21

Another test :

6
3 4 5 7 7 7

Output : 21

Another test :

5
10 10 9 8 7

Output : 27

You can try std::unordered_map to try and reduce the complexity even more.

Also see Why is "using namespace std;" considered bad practice?

Answer 2

The sum of a 3-element arithmetic progression is 3-times the middle element, so I would search around a middle element, and would start the search from the "upper" end of the "array" (and have it sorted). This way the first hit is the largest one. Also, the actual array would be a frequency-map, so elements are unique, but still track if any element has 3 copies, because that can become a hit (progression by 0).
I think it may be better to create the frequency-map first, and sort it later, simply because it may result in sorting fewer elements - though they are going to be pairs of value and count in this case.

function max3(arr){
  let stats=new Map();
  for(let value of arr)
    stats.set(value,(stats.get(value) || 0)+1);
  let array=Array.from(stats);       // array of [value,count] arrays
  array.sort((x,y)=>y[0]-x[0]);      // sort by value, descending
  for(let i=0;i<array.length;i++){
    let [value,count]=array[i];
    if(count>=3)
      return 3*value;
    for(let j=0;j<i;j++)
      if(stats.has(2*value-array[j][0]))
        return 3*value;
  }
}

console.log(max3([1,6,11,2,7,12]));  // original example
console.log(max3([3,4,5,7,7,7]));    // an example of 3 identical elements
console.log(max3([10,10,9,8,7]));    // an example from another answer
console.log(max3([1,2,11,6,7,12]));  // example with non-adjacent elements
console.log(max3([3,7,1,1,1]));      // check for finding lowest possible triplet too