How about putting all positive numbers in one group and negative in second group

Let $$$S$$$ denotes sum of element of array $$$a$$$.

Claim: Answer is $$$|S|$$$.

Proof: Let sum of all positive elements is $$$S_{pos}$$$ and sum of all negative elements $$$S_{neg}$$$. Put all positive numbers in first group and negative numbers in second group. We get $$$||S_{pos}| - |S_{neg}|| = |S|$$$.

Let's prove that we can not do better than that. Let $$$S_1$$$ denotes sum of elements of first group and $$$S_2$$$ denotes sum of elements of second group. We have $$$|S_1| - |S_2| \leq |S_1 + S_2| = |S|$$$. Hence $$$|S|$$$ is the upperbound for the answer.

// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 		int n; cin >> n;
 		int s = 0;
 		for(int i = 0; i < n; i++){
 			int x; cin >> x;
 			s += x;
 		}
 		cout << abs(s) << endl;
 return 0;	
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Instead of subsequences solve for substrings. That is there should not be any substring $$$\texttt{BAN}$$$ after performing operations.

In one operation you can destroy atmost $$$2$$$ substrings. Find minimum operations to destroy $$$n$$$ substrings.

Congrats, you have solved for subsequences also!

No subsequences of string $$$\texttt{BAN}$$$ would also mean no substrings of $$$\texttt{BAN}$$$ in original string. Let minimum number of operations to have no substrings of $$$\texttt{BAN}$$$ be $$$x$$$, it would be also be the lower bound for having no subsequences of string $$$\texttt{BAN}$$$.

Claim: $$$x = \left \lceil\frac{n}{2}\right \rceil$$$.

Proof: Swap $$$i$$$-th $$$\texttt{B}$$$ from start with $$$i$$$-th $$$\texttt{N}$$$ from end for $$$1 \leq i \leq \left \lceil\frac{n}{2}\right \rceil$$$. We can see that, no substrings of $$$\texttt{BAN}$$$ exists after performing $$$ \left \lceil\frac{n}{2}\right \rceil$$$ operations. Since we can only destroy atmost $$$2$$$ substrings in one operations, $$$\left \lceil\frac{n}{2}\right \rceil$$$ is minimum possible.

Now if you see clearly, after performing above operations, there does not exist any subsequence of string $$$\texttt{BAN}$$$ in original string. Hence $$$\left \lceil\frac{n}{2}\right \rceil$$$ is also the answer for the original problem.

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 		int n; cin >> n;
 		cout << n/2 + n % 2 << endl;
 		int l = 1, r = 3*n;
 		while(l < r){
 			cout << l << " " << r << endl;
 			l += 3;
 			r -= 3;
 		}
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Divide problem into two different cases. When $$$a_1 \gt \min(a)$$$ and when $$$a_1 = \min(a)$$$.

You do not need more hints to solve the problem.

Case 1: $$$a_1 \gt \min(a)$$$

$$$\texttt{Alice}$$$ can force the $$$\texttt{Bob}$$$ to always decrease the minimum element by always choosing minimum element of $$$a$$$ in her turn. Where as $$$\texttt{Bob}$$$ can not do much, all other elements he would swap with would be greater than or equal to $$$\min(a)$$$. Even if there exists multiple minimums in $$$a$$$, In first move $$$\texttt{Alice}$$$ would decrease from $$$a_1$$$, hence in this case $$$\texttt{Alice}$$$ would always win.

Case 2: $$$a_1 = \min(a)$$$

In this case optimal startegy for $$$\texttt{Bob}$$$ would be to always chhose minimum element of the array, which is $$$a_1$$$. $$$\texttt{Alice}$$$ would always be swapping the element greater than $$$a_1$$$ in her turn, hence in the case $$$\texttt{Bob}$$$ would always win

// Jai Shree Ram  
  
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,n)     for(int i=a;i<n;i++)
#define ll             long long
#define int            long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define endl           "\n"
#define x              first
#define y              second
#define gcd(a,b)       __gcd(a,b)
#define mem1(a)        memset(a,-1,sizeof(a))
#define mem0(a)        memset(a,0,sizeof(a))
#define sz(a)          (int)a.size()
#define pii            pair<int,int>
#define hell           1000000007
#define elasped_time   1.0 * clock() / CLOCKS_PER_SEC



template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}


int solve(){
 		int n; cin >> n;
 		vector<int> a(n);
 		for(auto &i:a)cin >> i;
 		sort(a.begin() + 1,a.end());
 		cout << (a[0] > a[1] ? "Alice" : "Bob") << endl;
 return 0;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #ifdef SIEVE
    sieve();
    #endif
    #ifdef NCR
    init();
    #endif
    int t=1;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}