0 like 0 dislike
1,656 views
Time Complexity should be O(N)  .

Example array :

k = 1 (number of swaps allowed)

{1,2,3,4} ..

Without any swaps the answer is : (2) : {2} and {4} are the only even sum disjoint subarrays .

If we do 1 swap of (2,3) , we get : 1,3,2,4 , and the answer is : (3) : {1,3} , {2} , {4} are the three disjoint even sum subarrays!
| 1,656 views 0 like 0 dislike

Ok, so the full solution depends on complicated observations...Lets try to find best answer for zero swaps, to maximize the number of even sum subarrays , we need to keep all even guys alone and merge 2 adjacent odd guys . For example, array a = [2,3,5,6,8,9,11] .

Best answer for this is :

{2},{3,5},{6},{8},{9,11}

I merged the odd guys and kept even guys alone which maximizes our answer .

So we know how to solve for k=0 swaps.

The problem only occurs when the odd guys appear for odd number of times in a continuous subarray .

Example , {3,5,7,2,11,13,15}

After making groups : {3,5} , {7} , {2}, {11} , {13,15}

We can see that 7 and 11 are in-valid guys

They make odd sum subarray we dont like it .

Using 1 swap, we can fix 2 such odd guys , so using k swaps you can fix 2k odd guys which are invalid .

So just fix the 2k odd guys and you are done!

Answer for 0 swaps is : 3 , but if we do 1 swap of (2,7), answer becomes 4 , {3,5},{2},{7,11},{13,15} . 4 even parts achieved!!

Say , we have : {odd1,even1,.................odd2} . We simply always swap even1 guy with odd2 guy and get : {odd1,odd2,.........even1} and hence 1 quantity of even sum subarray has increased ! Voila ! :-)

Its a common sense part that even and odd chunks of array gonna alternate , just find the total number of invalid off guys in the array and fix 2*k guys out of them

, the final array which u get is the best possible answer .

Code :

```#include <bits/stdc++.h>
using namespace std ;
typedef long long int ll ;
int main()
{

ll n ;
cin>>n ;
ll k ;
cin>>k ;
ll i = 0 ;
ll a[n+1] ;
while(i<=n-1)
{
cin>>a[i] ;
i++;
}
i=0;ll c = 0 ; ll d = 0 ;
ll e = 0 ; ll count = 0 ;
while(i<=n-1)
{

if(a[i]%2!=0)
{
c++;
}
else
{
d++;
if(c%2!=0)
{
count++;
}
e = e + c/2;
c=0;
}

i++;
}

if(c%2!=0)
{
count++;
}
e = e + c/2;

ll answer = d + e ;

ll god = 0 ;
god = min(count/2,k);