C++ Max Double Slice Sum
#include <algorithm>
#include <vector>
long long maxDoubleSliceSum(const std::vector<int>& a)
{
int size = static_cast<int>(a.size());
if (size < 3) {
return 0;
}
std::vector<long long> p1(size, 0);
std::vector<long long> p2(size, 0);
for (int i = 2; i < size - 1; ++i) {
p1[i] = std::max<long long>(0, p1[i - 1] + a[i - 1]);
p2[size - i - 1] = std::max<long long>(0, p2[size - i] + a[size - i]);
}
long long sum = p1[1] + p2[1];
for (int i = 1; i < size - 1; ++i) {
sum = std::max(sum, p1[i] + p2[i]);
}
return sum;
}
This keeps the best sum ending on the left and starting on the right, then combines them around each middle position.