- Array partition
- 2024-03-29 11:35:19 @

**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)

# 0 comments

# Information

- ID
- 1042
- Difficulty
- 7
- Category
- Beginners Click to Show
- Tags
- (None)
- # Submissions
- 22
- Accepted
- 8
- Accepted Ratio
- 36%
- Uploaded By