#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n , k;
	cin >> n >> k;
	ll arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	vector<ll> v;
	ll sum = 0;
	for(int i = 1; i < n; i++){
		v.pb(abs(arr[i] - arr[i-1]));
		sum += v.back();
	}
	sort(all(v));
	for(int groups = 1; groups < k; groups++){
		sum -= v.back();
		v.pop_back();
	}
	cout << sum << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()

void solve(){
	int n;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++)cin >> arr[i];
	int cur = arr[0];
	int part = 1;
	for(int i = 0; i < n; i++){
		cur &= arr[i];
		if(cur == 0){
			if(i == n-1)break;
			part++;
			cur = arr[i + 1];
		}
	}
	if(cur != 0)part--;
	part = max(part,1);
	cout << part << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	int t;cin >> t;while(t--)
	solve();
	return 0;
}

At the end of the array, you can only achieve xor of any subarray of the original array.

Now, we maintain a boolean array $$$b$$$ where $$$b_i$$$ is $$$1$$$ if there is some $$$j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$$$. Initially, $$$b$$$ is all $$$0$$$. We loop $$$j$$$ from $$$1$$$ to $$$n$$$ and check for each $$$k$$$ if $$$b_k=1$$$. If it is, then there is some position $$$p < j$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$$$. If we take xor of range from $$$(p,j]$$$, then it will be $$$k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ (as $$$a_1 \oplus a_2 \oplus \cdots \oplus a_p$$$ gets cancelled). This $$$a_1 \oplus a_2 \oplus \cdots \oplus a_j$$$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $$$n$$$ is large.

Time Complexity — $$$O(n \cdot 2^8)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &i : a)
            cin >> i;
 
        int const max_value = 1 << 8;
        vector<char> has_pref(max_value);
        has_pref[0] = true;
        int cur_xor = 0;
        int ans = 0;
        for (auto i : a) {
            cur_xor ^= i;
            for (int pref = 0; pref < max_value; ++pref) {
                if (has_pref[pref]) {
                    ans = max(ans, pref ^ cur_xor);
                }
            }
            has_pref[cur_xor] = true;
        }
 
        cout << ans << '\n';
    }
}