Prerequisite : Bruteforce
Problem statement summary : You are given an array. You need to find out maximum contiguous subarray such that each part has even sum or if it’s impossible then report it.
Solution :
1st Observation: If the total sum of the whole array is odd then it’s impossible to divide.
2nd Observation: If any position sum is even then we can divide it.
Let’s see an example, A [] = {2 3 1 4};
Current partition = 0;
Sum=0;
Start from index 1, sum+= A [1], sum=2, is even we can divide it, increase the current partition=1;
Index 2, sum+ =A[2] , sum= 5, is odd we cannot divide it.
Index 3, sum+=A [3], sum=6, is even we can divide it, increase the current partition =2;
Index4, sum+= A[4], sum= 10, is even we can divide it, increase the current partition =3;
So maximum even sum partition 3.
Time Complexity: O(n)