I have used a dp algo for spoj.pl/problems/LISA/
//code goes as below.
I keep getting WA , while I have checked it with most of the test cases which I found in this forum.
e.g 1+0*0+2 ( 3 1)
1+3*3+0 ( 12 10)
1+3+3*0 ( 4 0)
#include <stdio.h>
#include <math.h>
#include <iostream>
#include<new>
#include<algorithm>
#include<vector>
#include<typeinfo>
#include<map>
#include <fstream>
#include "string.h"
#include<cstdio>
#include<functional>
#include<algorithm>
#include <cassert>
#include <cstdlib>
#include <limits.h>
unsigned long long int getOp(unsigned long long int a , char b ,unsigned long long int c)
{
unsigned long long int r = 0;
if( b == '*')
r = a * c;
else
r = a+c;
return r;
}
int myatoi(char ch)
{
int r = ch - '0';
return r;
}
int main()
{
int test;
scanf("%d",&test);
char *input_g[5000];
for( int i = 0 ; i < test ; i++)
{
char t[100];
scanf("%s",&t);
input_g[i] = (char *)malloc(strlen(t)+1);
strcpy(input_g[i],t);
}
for( int i = 0 ; i < test ; i++)
{
//op is operator array and num is number array
//i.e if expression is 1+2*3+4 op = { +,* ,+} and num = {1,2,3,4}
char op[50] , num[50];
char input_l[100];
strcpy(input_l,input_g[i]);
//Array which stores max sum upto k elements;
//i.e sum[k] would contain max possible sum found upto kth number
unsigned long long int sum[50];
unsigned long long int m_sum[50];
char *p = &input_l[0];
int indx1 = 0, indx2 = 0;
for(; *p ;p++)
{
if( *p == '*' || *p== '+' )
{
op[indx1] = *p;
indx1++;
}
else
{
num[indx2] = *p;
indx2++;
}
}
op[indx1] = '\0';
num[indx2] = '\0';
char ch = op[0];
sum[0] = myatoi(num[0]);
m_sum[0] = myatoi(num[0]);
int l = strlen(num);
sum[1] = getOp(myatoi(num[0]),op[0],myatoi(num[1]));
m_sum[1] = getOp(myatoi(num[0]),op[0],myatoi(num[1]));
//simple dp loop.
for( int i = 2 ; i < l ; i++)
{
unsigned long long p = myatoi(num[i]);
unsigned long long int max = 0;
unsigned long long int min = ULLONG_MAX;
unsigned long long int t = 0;
unsigned long long int mt = 0;
for(int j = i ; j > 0 ; j--)
{
t = getOp(sum[j-1],op[j-1],p);
mt = getOp(m_sum[j-1],op[j-1],p);
if( t > max )
max = t;
if( mt < min )
min = mt;
p = getOp(myatoi(num[j-1]),op[j-1],p);
}
sum[i] = max;
m_sum[i] = min;
}
printf("%llu %llu",sum[indx1],m_sum[indx1]);
printf("\n");
}
return 0;
}
Some one please help 
