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&lt;stdio.h&gt;
#include&lt;string.h&gt;
#include&lt;math.h&gt;
#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;index&lt;=j;index++)
    {
        if(a[index])
            sweet++;
        else
            sour++;
    }
    if(sweet&gt;sour)
        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",&amp;test_cases);test_cases&gt;0;test_cases--)
    {       

        scanf("%d",&amp;number);
        for(i=0;i&lt;number;i++)
            for(j=0;j&lt;number;j++)
                m[i][j]=NEG_INFINITY;
        scanf("%s",&amp;buffer);
        for(i=0;i&lt;number;i++)
        {
            a[i]=buffer[i]-'0';
            m[i][i]=a[i];
        }
        for(l=2;l&lt;=number;l++)
        {       
            for(i=0;i&lt;number-l+1;i++)
            {
                j=i+l-1;
                for(k=i;k&lt;j;k++)
                {
                    if(sellable(a,i,j))
                        cost=j-i+1;
                    else
                        cost=m[i][k]+m[k+1][j];
                    if(cost&gt;m[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 &lt; 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 &gt; (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.