Brute Force and Complete Search

Brute force systematically checks every allowed candidate. It is often the best first solution: easy to justify, useful on small constraints and valuable as an independent testing oracle for faster algorithms. This lesson finds the largest sum of two distinct array positions by examining every unordered pair. It illustrates complete coverage, duplicate values and the difference between an invalid pair and a negative but valid answer.

Prerequisites: Nested loops; vectors; complexity analysis.

Build the idea

1. 1. Define the candidate space

   We choose indices i and j with 0≤i<j<n. The condition excludes using one position twice and avoids checking the same unordered pair in both orders. Equal VALUES at different indices are still distinct choices. If n<2, there is no candidate at all; report NONE rather than inventing a zero-valued pair.

2. 2. Maintain an exact invariant

   After each checked pair, best is the largest pair sum seen so far. Initialize from a real pair a[0]+a[1], not zero, because every valid sum may be negative. For each candidate sum, replace best only if larger. At termination every legal pair has been considered, so this invariant proves global optimality.

3. 3. Trace a sample

   For [5,−2,7,7], pair sums are 3,12,12,5,5,14. The last pair uses the two different positions containing 7, giving 14. A solution that removes duplicate VALUES before searching would incorrectly discard one usable position. On [−5,−2], the only valid answer is −7, not zero.

   Index pair	Sum
   0,1	3
   0,2	12
   0,3	12
   1,2	5
   1,3	5
   2,3	14

4. 4. Decide whether complete search fits

   The number of pairs is n(n−1)/2. For n=2000 it is about two million, manageable for a simple teaching example; for n=200000 it is about twenty billion and inappropriate. Constraints should guide whether a quadratic approach is acceptable. The same idea extends to triples or subsets, but candidate counts grow much faster.

5. 5. Improve only after establishing a baseline

   This particular task can be solved by tracking the largest two values at distinct positions in one scan, O(n) time and O(1) working memory. Keeping the brute-force implementation remains useful for random small-input comparisons. An optimization is valid because of a property of the objective—the best pair consists of two largest elements—not because all pair problems admit the same shortcut.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>a(n);
    for(long long&x:a){
        std::cin>>x;
    }
    if(n<2){
        std::cout<<"NONE\n";
        return 0;
    }
    long long best=a[0]+a[1]; // A real candidate handles all-negative input.
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            if(a[i]+a[j]>best){
                best=a[i]+a[j];
            }
        }
    }
    std::cout<<best<<'\n';
}

Complexity analysis

O(n²) time from n(n−1)/2 candidates, O(n) total storage for the input, and O(1) auxiliary space beyond it. Each candidate takes constant-time arithmetic. With n≤2000 and |aᵢ|≤10^9, both runtime and long-long pair sums are safe.

Example input and output

Read n (0..2000), then n integers |value|≤10^9. Print the maximum sum of two distinct positions, or NONE when n<2.

Input

4
5 -2 7 7

Output

14

The two separate positions holding 7 form the best pair.

Practical applications

Use complete search for genuinely small inputs, tiny candidate spaces, prototypes and reference testing. Backtracking organizes dependent choices and prunes impossible partial candidates. Meet in the middle or DP may help when full enumeration is too large, but only after identifying the relevant structure.

Check your understanding

Why start the inner index at i+1?

Put it into practice

Write the O(n) two-largest-values version and compare it with this baseline.