Я пытаюсь отобразить элементы в массиве, которые суммируются с максимальным числом, и никакие два элемента не являются последовательными (смежными).
Я понял, как рассчитать максимальную сумму, поддерживая сумму включительно и эксклюзивный элементов массива. Есть ли оптимизированный способ захватить все элементы, составляющие максимальную сумму, и отобразить ее в обратном порядке?
Код :
int i_sum = tickets[0];
int e_sum = 0;
int new_sum = 0
int sum = 0;
for (int i = 1; i < n; i++)
{
new_sum = (i_sum > e_sum) ? i_sum : e_sum;
i_sum = e_sum + tickets[i];
e_sum = new_sum;
}
(i_sum >= e_sum) ? std::cout << "incl " << i_sum : std::cout << "excl " << e_sum;
Например :
п = 8
массив = [100, -3, 200, 50, 400, -7, 20, 80]
максимальная сумма = 780
выход : 80 400 200 100
И если и включающая, и исключительная сумма одинаковы, выход будет тот, у которого установлен больший элемент.
Случай :
п = 4
массив = [4, 5, 4, 3]
максимальная сумма = 8
выход : 4, 4
Должен ли я поддерживать два разных массива для хранения всех возможных значений или вставлять их по одному на каждом проходе?
Заранее спасибо.
Да, вы можете поддерживать два массива, копировать и менять их местами на каждом этапе. Однако это не оптимально. Это сделает ваш алгоритм О (п2).
std::vector<int> incl, excl;
if (tickets[0] > 0)
incl.push_back(tickets[0]);
for (int i = 1; i < n; i++)
{
std::vector<int> temp;
if (i_sum > e_sum) {
new_sum = i_sum;
} else {
new_sum = e_sum;
temp = excl;
}
i_sum = e_sum + tickets[i];
e_sum = new_sum;
excl.push_back(tickets[i]);
std::swap(incl, excl);
if (temp.size())
excl = temp;
}
incl
или excl
будет содержать ваше решение в зависимости от того, что больше.
Я сделал небольшую оптимизацию, используя std::swap
, чтобы использовать семантику перемещения, которая позволяет избежать копирования, но когда e_sum > i_sum
, мы не можем избежать копирования temp
в excl
.
Вместо этого, сформулировав ту же задачу с помощью динамического программирования, вы можете выполнить это в На). Идея похожа. Либо вы включаете текущий элемент и добавляете к решению максимальную сумму второго предыдущего элемента, либо исключаете текущий элемент, чтобы получить решение для предыдущего элемента. Код следующим образом:
vector <int> dp(n);
vector <int> parent(n, 0);
if (tickets[0] > 0) {
dp[0] = tickets[0];
parent[0] = tickets[0];
}
if (tickets[1] > 0) {
dp[1] = tickets[1];
parent[1] = tickets[1];
}
for (int i = 2; i < n ; i++) {
if (dp[i-1] > tickets[i] + dp[i-2]) {
dp[i] = dp[i-1];
} else {
dp[i] = tickets[i] + dp[i-2];
parent[i] = tickets[i];
}
}
cout << "Max sum: " << dp[n-1] << endl;
for(int i = n - 1; i >= 0;) {
if (parent[i]) {
cout << parent[i] << ' ';
i = i - 2;
} else {
i--;
}
}
parent
вектор можно использовать для отслеживания шагов, предпринятых для решения динамического программирования.
В качестве примечания, решение, упомянутое в вашем вопросе, немного неверно. Если первый элемент отрицательный, вы получите неоптимальный результат.
Ошибка — это первая строка вашего кода. int i_sum = tickets[0];
. Вы включаете его, не проверяя на наличие негатива. В остальном мой алгоритм такой же, как у вас.
Это работает как шарм, спасибо. На заметку, поправьте меня, если я ошибаюсь, я вижу, вы сделали то же самое, чтобы уклониться от любого отрицательного числа.