O(n) solution without using DP


#1

int n = A.size();
if(n==0)
return 0;
if(n==1)
return 1;
int index = 0;
if(A[index]==0)
return 0;
//int max = A[0],max_ind = 0;
int target = n-1;
index = n-2;
while(index>=0)
{
if(A[index]-(target-index)>=0) //see if target index can be reached by any index before it
{
target = index;
index–;
}
else
index–;
}
if(target==0)
return 1;
else
return 0;