Simple solution without dp using kadens algorithm concept


#1

int Solution::maxProduct(const vector &A) {
int n=A.size();
int result=A[0];
int max_until=1;
int curr_max=1;
for(int i=0;i<n;i++)
{
max_until=max_untilA[i];
curr_max=curr_max
A[i];
result=max(result,max(curr_max,max_until));
if(curr_max==0)
curr_max=1;
if(max_until==0)
max_until=1;
else if(curr_max<0)
{
if(i+1<n && A[i+1]>0)
curr_max=1;
}

}
return result;

}