Find the largest subarray in an array whose sum is odd | Google | Amazon

Question

Example array : {0,1,1,1,-5,2,-4} .

Answer = {1,1,-5,2,-4}  is the largest subarray whose sum is odd.

Rules :

1)Explanation of algorithm in your answer is a must .

2)Writing code is optional .

3)If code is written , make sure to you use format option from the editor .

Answer 1

1. Calculate prefix sum and store it in a new array.
2. A. If the last element is odd, then return the array.

           B. If not, then

                   I. Find out the last odd sum in prefix array and take the length from first to last odd sum.

                   II.  Find out the first odd sum in the prefix array and then take the length of the array from the first odd sum to the last element.

       3. Return the array with a maximum length