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.

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 (solving this on an online judge), 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?