C_Yarik_and_Array.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
#ifndef ONLINE_JUDGE
	freopen("Error.txt", "w", stderr);
#endif

	int t = 1; // Number of test cases
	cin >> t;

	while (t--) {
		ll n; // Length of the array
		cin >> n;
		vector<ll> v(n); // Array to store elements

		// Reading the array elements
		for (int i = 0; i < n; i++) { // O(n)
			cin >> v[i];
		}

		ll ans = INT_MIN; // Variable to store the maximum sum of subarray
		int i = 0, j = 0; // Pointers for the start and end of the subarray
		ll sum = 0; // Current sum of the subarray

		// Iterate over the array to find the maximum sum subarray with alternating parities
		while (j < n) { // O(n)
			// Reset sum if it becomes negative
			if (sum < 0) {
				sum = 0;
				i = j;
			}

			// Check if the current element can be added to the subarray
			if (i < j) {
				// Check if the current and previous elements have alternating parities
				if ((v[j] ^ v[j - 1]) & 1) {
					sum += v[j];
				} else {
					sum = v[j];
					i = j;
				}
			} else {
				sum = v[j];
			}

			// Update the maximum sum found so far
			ans = max(ans, sum);
			j++;
		}

		// Output the maximum sum for the current test case
		cout << ans << endl;
	}

	// Time Complexity (TC): O(n)
	// Space Complexity (SC): O(n)
}











/*
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = a; i < b; i++)

void solve() {

}

int main() {
    fastio;

    int t;
    cin >> t;
    while (t--) {
         int n;
        cin>>n;
        vector<pair<int  , char>> arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i].first;
            if(arr[i].first%2!=0) arr[i].second = 'O';
            else arr[i].second = 'E';

        }
        int l = 0 , r = 0;
        int sum = arr[0].first ;
        int  ori = arr[0].first;

        while(l<n){
            ori = max(ori , sum);
            if(r+1<n && arr[r].second != arr[r+1].second){
                r++;
                sum+=arr[r].first;
                //cout<<"cc"<<endl;
            }
            else if(r<n && l<r){

                int temp = sum;
                for(int i = r;i>=l;i--){
                    int temp2 = temp;
                    //cout<<"till "<<i<<" ";
                    for(int x = l;x<=i;x++){
                        //cout<<"from "<<x<<" ";
                        temp2-=arr[x].first;
                        ori = max(ori , temp2);
                    }
                    //cout<<endl;
                    // cout<<temp2<<" ";
                    temp-=arr[i].first;

                }
                r++;
                l = r;
                if(l<n) sum = arr[l].first;
                //cout<<l<<endl;
                if(l<n) ori = max(arr[l].first , ori);
            }
            else if(l==r && r+1<n){
                r++;
                l = r;
                sum = arr[l].first;


            }
            else break;
            ori = max(ori , sum);

        }
        cout<<ori<<endl;
    }

    return 0;
}



*/