I've been trying to understand Dynamic Programming lately, here's the question I just attempted:
You are given an array A of N positive integer values. A subarray of this array is called an Odd-Even subarray if the number of odd integers in this subarray is equal to the number of even integers in this subarray.
Find the number of Odd-Even subarrays for the given array.
Solving this on hackerearth, here!
I immediately connected this with Matrix-Chain Multiplication from CLRS, which tries all sub-arrays. To optimise it for this question, I used the numEvens array to track number of even ints from index 0 to i. This takes \$O(n)\$ time. This way I don't have to actually scan every sub-array to see if it's Odd-Even or not. evensIJ tells me how many even ints are in arr[i..j]. I still have to visit every sub-array though, thus the \$O(n^2)\$ nested loops, where l is the length of the sub-array.
Here's the code, it takes as input the array arr of ints and it's size n:
long int numArrs(int arr[], int n)
{
int numEvens[n], l, i, j, evensIJ;
if (arr[0] & 1) numEvens[0] = 0;
else numEvens[0] = 1;
for (i = 1; i < n; i++)
numEvens[i] = (arr[i] & 1) ? (numEvens[i - 1]) : (1 + numEvens[i - 1]);
long int count = 0;
for (l = 2; l <= n; l += 2)
{
if (l > n) break;
for (i = 0; i < n - l + 1; i++)
{
j = i + l - 1;
evensIJ = numEvens[j] - numEvens[i] + ((arr[i] & 1) ? 0 : 1);
if (2*evensIJ == (j - i + 1))
count++;
}
}
return count;
}
I believe my code is correct but it give a Time Limit Exceeded error on larger test cases, even though it solves all smaller ones correctly. Any way to optimise it? Should I completely abandon this approach or should I optimise on this approach somehow?
Any style advise is also appreciated since I've been coding in Python3 for the last two years and have just shifted to C++14 last week because I need speed for competitive coding and all.
Also, side note, changing
evensIJ = numEvens[j] - numEvens[i] + ((arr[i] & 1) ? 0 : 1);
to
evensIJ = numEvens[j] - numEvens[i - 1];
makes the code incorrect. Am I being dumb for not getting why this happens?