given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

given an array of positive numbers and negative numbers devise an algo to find max non-consecutive sum in that array. complexity should be in o(n).

s(i)=max{s(i-1),s(i-2)+a[i]} if(a[i]>0)
s(i)=s(i-1) if(a[i]<0)

int f(int* a,int n)//this is recursive way, which is O(2^n)
{
 if(n<0) return 0;
 if(a[n]>0)
  return max(f(a,n-1),f(a,n-2)+a[n]);
 return f(a,n-1);
}

int b[9]={0};
int f2(int* a,int n)//this is dp, which is O(n)
{
 if(n<0) return 0;
 if(a[n]>0)
 {
  //if(b[n-1]&&b[n-2])
  // return max(b[n-1],b[n-2]+a[n]);
  //if(b[n-1])
  // return max(b[n-1],f(a,n-2)+a[n]);
  //if(b[n-2])
   return max(f(a,n-1),b[n-2]+a[n]);
 }
 else
 {
  if(b[n-1]) return b[n-1];
  else return f(a,n-1);
 }
}

int main()
{
 int a[9]={1,-2,3,4,-1,6,5,2,4};
 cout<<f(a,8)<<endl;
}