Блог пользователя sanjay6969

Is this approach correct ?? any optimization for this problem?
Автор sanjay6969, 8 месяцев назад, По-английски

Is my approach correct? can anyone have more optimised approach?

my code:


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int signal_size;
    cin >> signal_size;

    vector<int> signals(signal_size);
    for (int i = 0; i < signal_size; ++i) {
        cin >> signals[i];
    }

    int filter_A_sum = 0;
    int filter_B_sum = 0;

    int left = 0, right = signal_size - 1;

    bool is_A_turn = true;

    while (left <= right) {
        if (is_A_turn) {
            if (signals[left] > signals[right]) {
                filter_A_sum += signals[left];
                ++left;
            } else {
                filter_A_sum += signals[right];
                --right;
            }
        } else {
            if (signals[left] > signals[right]) {
                filter_B_sum += signals[left];
                ++left;
            } else {
                filter_B_sum += signals[right];
                --right;
            }
        }

        is_A_turn = !is_A_turn;
    }

    cout << filter_A_sum << endl;

    return 0;
}
  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

your approach is wrong as well as sample test 2 is also incorrect. we can do this problem using O(n^2) dp.

code
→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

This problem is solvable in $$$\Theta(N)$$$ via a greedy algorithm.

Spoiler
→ Ответить