Your baseline code is a good starting point because it (mostly) works, but there are some things that could be improved.
Don't abuse using namespace std
Putting using namespace std
at the top of every program is a bad habit that you'd do well to avoid. I don't know that you've actually done that, (you might have used the slightly more enlightened using std::vector;
) but it's an alarmingly common thing for new C++ programmers to do.
Avoid arbitrary "magic numbers"
The number 1000
in your code is somewhat suspect. Where did it come from? Why 1000 instead of 10000 or -9? It's better to declare some named const
, or even better, use an already existing constant such as std::numeric_limits<int>::max()
.
Use const
wherever you can
You could (and should) use const
for the vector that you're passing to your routine, and you can also use it for n
because it is only initialized once and never changed.
Consider generality where practical
The code currently only accepts a std::vector
of int
values and would require changes if it were used with, for example a std::vector
of float
values. Because this is a mechanism that would be appropriate for many different kinds of numeric values, consider using a templated class instead.
Consider your algorithm carefully
Other answers have provided alternate ways of doing the calculation, but require more memory. There is another way of doing this which is fairly simple. Consider your original code in which you have an lsum
and rsum
value at some arbitary point in the vector. If we consider the values \$l\$ and \$r\$ to be the lsum
and rsum
values and \$d\$ to be the value difference
(without the absolute value), then advancing to the next index array and calculating \$l'\$ and \$r'\$ and \$d'\$ can be done like this:
$$\begin{eqnarray}
d &=& r - l \\
r' &=& r - i \\
l' &=& l + i \\
d' &=& r' - l' \\
&=& (r - i) - (l + i) \\
&=& r - i - l - i \\
&=& r - l - 2i \\
&=& d - 2i
\end{eqnarray}$$
This result means that there is no need to store the lsum
and rsum
values, nor is there a need to create an additional vector of partial sums.
Try to use descriptive names
I didn't find much use in the name solution
for the function. It may be accurate but it doesn't convey much meaning to other programmers. Consider that it's a minimum partial sum so maybe a better name would be minpsum
? I'm not sure that's a huge improvement, but maybe you can come up with something better. Also A
is arguably not a great name, but if we consider it to be short for Array
than it's at least defendable.
Result
So we can effectively apply all of these ideas into a routine like this:
template <typename T>
T minpsum(const std::vector<T> &A) {
if (A.empty()) {return std::numeric_limits<T>::max();}
T posdiff{std::accumulate(A.cbegin(), A.cend(), T(0))};
const T zero{0};
T diff=posdiff;
T negdiff{-posdiff};
if (posdiff < zero)
std::swap(negdiff, posdiff);
for (const auto &i : A) {
diff -= (i+i);
if (diff < zero && diff > negdiff) {
negdiff = diff;
} else if (diff > zero && diff < posdiff) {
posdiff = diff;
}
}
negdiff = -negdiff;
return posdiff < negdiff ? posdiff : negdiff;
}
As you can see, there is no longer a call to abs
because that would assume int
arguments and I wanted to make the code generic, accepting float
or double
or whatever as a templated function. I have also used the C++11 range operator and std::accumulate
with const
iterators. We can try it out with the following driver code:
int main()
{
std::vector<int> vec(1000);
std::iota(vec.begin(), vec.end(), -200);
int s = minpsum(vec);
std::cout << s << '\n';
assert(s == 394);
}
This version of the code will work with the fundamental math types but not with something like std::complex<std::double>
because the latter type does not implement the comparison operators <
and >
which are required by this code.
Limitations
It should be noted that there is a chance of overflow or numeric wraparound when this code is used. The assumption made in the code is that the type T
is sufficient to not only hold each member of the array, but also the sum of all of them, which may or may not be valid.
Also, because of the subtraction, there is the potential for unsigned numbers to "wrap" around 0. That is, \$3 - 5 = -2\$, but \$-2\$ is not representable as an unsigned number. Caveat lector.