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<stdio.h>#include<string.h>#include<math.h>#define MAX 210#define NEG_INFINITY -1000int sellable(int a[MAX], int i, int j){    int index,sweet=0,sour=0;    for(index=i;index<=j;index++)    {        if(a[index])            sweet++;        else            sour++;    }    if(sweet>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,&test_cases);test_cases>0;test_cases--)    {               scanf(%d,&number);        for(i=0;i<number;i++)            for(j=0;j<number;j++)                m[i][j]=NEG_INFINITY;        scanf(%s,&buffer);        for(i=0;i<number;i++)        {            a[i]=buffer[i]-'0';            m[i][i]=a[i];        }        for(l=2;l<=number;l++)        {                   for(i=0;i<number-l+1;i++)            {                j=i+l-1;                for(k=i;k<j;k++)                {                    if(sellable(a,i,j))                        cost=j-i+1;                    else                        cost=m[i][k]+m[k+1][j];                    if(cost>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?
SPOJ is giving TLE for this solution of ROCK
optimization;algorithm;c;programming challenge
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 asif (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 justreturn (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.