Adding two sides of an array

The purpose of the program is to add 2 sides of an array starting from the bottom and top of both ends and to find the lowest difference at equal decrements of iteration. The program functions but it's slow.

int solution(vector &A) {
    int n = A.size();
    int i, j, rsum, lsum, difference;
    int currentmindifference = 1000;

    for(i = 0; i < n; i++)
    {
        lsum = 0;
        rsum = 0;
        for(j = 0; j <= i; j++) lsum += A[j];
        for(j = i + 1; j < n; j++) rsum += A[j];
        difference = abs (lsum - rsum);
        if (difference < currentmindifference) currentmindifference = difference;
    }

    return currentmindifference;
}

Your code is \$O(n^2)\$. You can improve it to \$O(n)\$ by precomputing a sum array.

int solution(vector &A) {
    int n = A.size();
    int i, j, rsum, lsum, difference;
    int currentmindifference = 1000;

    std::vector pre(n);
    pre[0] = A[0];
    for (i = 1; i < n; i++)
        pre[i] = pre[i - 1] + A[i];

    for(i = 0; i < n; i++)
    {
        lsum = pre[i];
        rsum = pre[A.size() - 1] - lsum;
        difference = abs (lsum - rsum);
        if (difference < currentmindifference) currentmindifference = difference;
    }

    return currentmindifference;
}

Reasoning. By calculating a sum array, we save the need to calculate lsum on each iteration. Furthermore, we notice that we can find rsum by finding the total sum less lsum.

We can simplify this further by noting that lsum and rsum are now superfluous. We will also replace 1000 with std::numeric_limits::max() to ensure we get a true minimum instead of capping it, and check if A is empty before using it.

#include 
#include 
#include 
#include 

int solution(std::vector &A) {
    if (A.empty())
        return -1; // or some other meaningful error value

    int n = A.size();
    int minDifference = std::numeric_limits::max();

    std::vector pre(n);
    pre[0] = A[0];
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + A[i];

    for (int i = 0; i < n; i++)
        minDifference = std::min(minDifference, std::abs(2 * pre[i] - pre[n - 1]));

    return minDifference;
}

Further reading: Prefix sum array and difference array. Disclosure: I am an administrator on this site. Excuse the formatting.

StackExchange Code Review Q#57813, answer score: 6