Брат это NP полная задача, лучшее решение за O(2^n). Если хочешь решить это за адекватное время, то прочитай о алгоритм "Отжига"

could it be like a knapsack prob???

I think this solution may work , only because we have N positive integers in the array at the initial state .

Make a segment tree for the given array

Now make a copy of original array and sort it.Doing so we help to give us the smallest number to run our check function.

Now starting from the smallest number, find the fist occurrence from right side (greedy approach), check if it can be turned into negative with the help of segment tree ( get sum 0,i ) and if its True, turn it and update the segment tree with update( i, -2*a[i] ) and ans++.

If its a False, skip this number and move on to the next ... do so for all

ig can be done with heaps

would be happy if someone finds some wrong testcase, cause greedy's are weird

void solve(){
    int n;cin>>n;
    vector<int> a(n);
    for(int&x:a) cin>>x;
    priority_queue<int> neg;
    neg.push(-1e18);
    priority_queue<int,vector<int>,greater<int>> pos;
    pos.push(1e18);
    int sum=0;
    int count=0;
    for(int i=0;i<n;i++){
        while(pos.top()<neg.top()){
            int x=pos.top();
            int y=neg.top();
            neg.pop();
            pos.pop();
            sum-=x;
            sum+=y;
            pos.push(y);
            neg.push(x);
        }
        if(sum-a[i]>0){
            sum-=a[i];
            neg.push(a[i]);
            count++;
        }else{
            pos.push(a[i]);
            sum+=a[i];
        }
    }
    cout<<count<<endl;
}

let mut sum = 0;
let mut q = BinaryHeap::new();
for a in aa {
    q.push(a);
    sum -= a;
    if sum <= 0 {
        sum += 2 * q.pop().unwrap();
    }
}

println!("{}", q.len());

Who else failed to solve this problem during Amazon OA test.

I already have a blog : Time Travel in Greedy Algorithms and practice problems on this topic.

play genshin impact

Brute Force (DP) Solution:
The first approach you might consider is using a turn / not-turn (pick/unpick) DP.

We maintain two states:
* The current index
* The prefix sum so far

At each state, you can always choose not to turn the number negative.
If adding the negative of the current index to the prefix sum keeps it positive
(i.e., current_sum - nums[index] > 0), you can also choose to turn this number negative.

The result is the maximum of the two options.
With memoization, the time complexity will be O(N^2) (since the prefix sum can be as large as 1e5).
This is too slow. So if DP doesn't work, let's consider a greedy approach.

Greedy (Optimal) Solution:
* We cannot turn the first element negative, since that would make the prefix sum negative immediately.
* Start with prefix_sum = nums[0].
* Traverse the remaining elements:

1. Try turning the current number negative. — If doing so keeps the prefix sum positive, update prefix_sum -= nums[i] and increase the count.

2. If turning the current number negative makes the prefix sum non-positive, but we already turned some larger number negative earlier:
— Turn that larger(maximum of all) number back to positive, and turn the current (smaller) number negative instead.
— This keeps the prefix sum larger for future operations.

1. If we haven't turned any number negative yet, and changing the current number makes the prefix sum non-positive:

• Do nothing; just update the prefix sum and continue.

To get the maximum of numbers turned negative, we can use a max heap.
This gives us a time complexity of O(N log N).

Python Implementation

from heapq import heappush, heappop

def solve(nums):
    max_heap, prefix_sum, turned_on = [], nums[0], 0

    for i in range(1, len(nums)):
        if prefix_sum - nums[i] > 0:
            turned_on += 1
            prefix_sum -= nums[i]
            heappush(max_heap, -nums[i])

        elif max_heap and abs(max_heap[0]) > nums[i]:
            prefix_sum -= 2 * heappop(max_heap)
            prefix_sum -= nums[i]
            heappush(max_heap, -nums[i])

    return turned_on