嗯，我有我的解決方案，可能不是最好的一個工具100％有效，根據codility requierments。
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
typedef unsigned int uint;
void unifySums(const std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & sums,
const std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & betweenSums,
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & unifiedSums,
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & betweenUnifiedSums
)
{
for (uint i = 0; i < betweenSums.size(); i++) {
uint j = i;
int partSum = sums[j].second.first;
int min = sums[j].first.second;
while ((j < betweenSums.size()) && std::abs(sums[j].second.first) >= std::abs(betweenSums[j].second.first) &&
std::abs(sums[j + 1].second.first) >= std::abs(betweenSums[j].second.first)) {
partSum += betweenSums[j].second.first + sums[j + 1].second.first;
if (min > betweenSums[j].second.second)
min = betweenSums[j].second.second;
++j;
}
if (j != i) {
unifiedSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(sums[i].first.first, sums[j].first.second),
std::pair<int, int>(partSum, min))
);
if (j < betweenSums.size())
betweenUnifiedSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(betweenSums[j].first.first, betweenSums[j].first.second),
std::pair<int, int>(betweenSums[j].second.first, betweenSums[j].second.second))
);
i = j;
continue;
}
unifiedSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(sums[i].first.first, sums[i].first.second),
std::pair<int, int>(sums[i].second.first, sums[i].second.second))
);
betweenUnifiedSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(betweenSums[i].first.first, betweenSums[i].first.second),
std::pair<int, int>(betweenSums[i].second.first, betweenSums[i].second.second))
);
}
if (unifiedSums[unifiedSums.size() - 1].first.second < sums[sums.size() - 1].first.second) {
unifiedSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(sums[sums.size() - 1].first.first,
sums[sums.size() - 1].first.second),
std::pair<int, int>(sums[sums.size() - 1].second.first, sums[sums.size() - 1].second.second))
);
}
}
void createSums(const std::vector<int> & vec,
const double & avg,
int & maxSum,
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & sums,
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> & betweenSums)
{
const uint len = vec.size();
for (uint i = 1; i < len - 1; i++) {
int partialSum = 0;
uint j = i;
int min = vec[j];
while ((j < len - 1) && ((double)vec[j] < avg && vec[j] < 0)) {
partialSum += vec[j];
if (min > vec[j])
min = vec[j];
++j;
}
if (j > i) {
--j;
if (sums.size() == 0) {
i = j;
continue;
}
betweenSums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(i, j), std::pair<int, int>(partialSum, min))
);
i = j;
continue;
}
while ((j < len - 1) && (((double)vec[j] >= avg && vec[j] < 0) || vec[j] >= 0)) {
partialSum += vec[j];
if (min > vec[j])
min = vec[j];
++j;
}
if (j > i) {
j--;
}
sums.push_back(
std::pair<std::pair<uint, uint>, std::pair< int, int>>(std::pair<uint, uint>(i, j), std::pair<int, int>(partialSum, min))
);
i = j;
if (maxSum < partialSum)
maxSum = partialSum;
}
if (betweenSums.size() == sums.size()) {
betweenSums.pop_back();
}
}
int solution(std::vector<int> & A)
{
const std::size_t len = A.size();
if (len < 4)
return 0;
int max = A[1];
int min = A[1];
int sum = A[0];;
uint minIndex = 1;
for (uint i = 1; i < len - 1; i++) {
sum += A[i];
if (A[i] > max)
max = A[i];
if (A[i] < min) {
min = A[i];
minIndex = i;
}
}
sum += A[len - 1];
if (max <= 0)
return 0;
if (min >= 0) {
return sum - A[0] - A[len - 1] - A[minIndex];
}
const double avg = (double)sum/len;
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> sums;
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> betweenSums;
std::pair<int, int> partSum;
int maxSum = min;
createSums(A, avg, maxSum, sums, betweenSums);
if (sums.size() == 1) {
return sums[0].second.first;
}
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> unifiedSums;
std::vector<std::pair<std::pair<uint, uint>, std::pair<int, int>>> betweenUnifiedSums;
unifySums(sums, betweenSums, unifiedSums, betweenUnifiedSums);
if (betweenUnifiedSums.size() == 0) {
if (unifiedSums[0].second.first > (unifiedSums[0].second.first - unifiedSums[0].second.second))
return unifiedSums[0].second.first;
else
return unifiedSums[0].second.first - unifiedSums[0].second.second;
}
for (uint i = 0; i < betweenUnifiedSums.size(); i++) {
int minSoFar = betweenUnifiedSums[i].second.second;
int sumSoFar = unifiedSums[i].second.first + betweenUnifiedSums[i].second.first + unifiedSums[i+1].second.first;
if (unifiedSums[i].second.first - unifiedSums[i].second.second > maxSum)
maxSum = unifiedSums[i].second.first - unifiedSums[i].second.second;
if (sumSoFar - minSoFar > maxSum)
maxSum = sumSoFar - minSoFar;
if (std::abs(betweenUnifiedSums[i].second.first) - std::abs(betweenUnifiedSums[i].second.second) >= std::abs(sumSoFar))
continue;
for (uint j = i + 1; j < betweenUnifiedSums.size(); j++) {
if (betweenUnifiedSums[j].second.second < minSoFar)
minSoFar = betweenUnifiedSums[j].second.second;
sumSoFar += betweenUnifiedSums[j].second.first + unifiedSums[j + 1].second.first;
if (sumSoFar - minSoFar > maxSum)
maxSum = sumSoFar - minSoFar;
if (std::abs(betweenUnifiedSums[j].second.first) - std::abs(betweenUnifiedSums[j].second.second) >= std::abs(sumSoFar))
break;
}
}
return maxSum;
}
謝謝阿布舍克。這是一個優雅的解決方案。 –
輝煌的解決方案，阿布舍克。通過查找最大化其左右最大序列之和的索引來搜索「Y」值。 – AndyG
@AndyG謝謝.. :) –