SPOJ is giving TLE for this solution of ROCK

I am solving ROCK problem on SPOJ. I have used bottom up dynamic programming approach for this problem. Time complexity for this is \$O(n^3)\$.

#include
#include
#include
#define MAX 210
#define NEG_INFINITY -1000

int sellable(int a[MAX], int i, int j)
{
    int index,sweet=0,sour=0;
    for(index=i;indexsour)
        return 1;
    return 0;
}
int main()
{
    int test_cases,i,j,k,length,l;
    int number,cost;
    int a[MAX];
    int m[MAX][MAX];
    char buffer[MAX];

    for(scanf("%d",&test_cases);test_cases>0;test_cases--)
    {       

        scanf("%d",&number);
        for(i=0;im[i][j])
                    {
                        m[i][j]=cost;
                    }
                }
            }
        }
        printf("%d\n",m[0][number-1]);
    }
    return 0;
}

Can you please suggest an alternative approach for this problem, or if any changes can be made in my code?

The way you call sellable may amount to a 4-th degree complexity. The very smart compiler may notice that it is a pure function, and optimize it out of the inner loop, but I wouldn't rely on it. So, one obvious optimization is to rephrase it as

if (sellable(a, i, j)) {
    cost = j - i + 1;
} else {
    cost = m[i][j];
    for (k = i; k < j; k++) {
        cost = max(cost, m[i][k] + m[k+1][j]);
}
m[i][j] = max(m[i][j], cost);

Still, sellable contributes to the cubic complexity. With a one-time linear investment you can make it into a constant time. Collect accumulated sums [0, i) of the input array; then sellable becomes just

return (a[j] - a[i]) * 2 > (j - i);

The mandatory CR note on the variable names: one letter identifiers make it really hard to follow the code, even as simple as this. I would recommend to use length, seg_start, seg_end instead of l, i, j respectively. number is just meaningless; size sounds better.

Then, I'd highly recommend to interpret length as length (not length + 1 as your code does).

Finally, please don't be shy on spaces.

StackExchange Code Review Q#56587, answer score: 3