c - Modify any element of the array -

given array of integers , can modify of number of arbitrary positive integer , , makes entire array strictly increasing , positive integers , , asked @ least need change few numbers

input: 5 1 2 2 3 4

output: 3

and there have tried ,each number in order reduce more ( first number minus 1 , second number minus 2 ,the third number minus three)

    #include <stdio.h>     int modify_the_array(int b[],int n);     int max(int a,int b);     int main(int argc,char *argv) {          int before_array[]={1,2,3,4,1,2,3,4,5};         int len=sizeof(before_array[0])/sizeof(before_array);         int b;         b=modify_the_array(before_array,len);         printf("%d\n",b);         return 0;     }      int max(int a,int b){         return a>b?a:b;     }      int modify_the_array(int b[],int len) {         int i,b=0,n=1;         int maxsofar,tmp,j;         (i=0;i<len;i++){             b[i]=b[i]-n;             n++;          }          maxsofar=0;         tmp=0;         for(i=0;i<len;i++) {             (j=i+1;j<len;j++) {             if (b[j]==b[i]&&b[i]>1) {                 maxsofar=max(maxsofar,++tmp);                 b=len-maxsofar;             }         }     }         return b; } 

somebody recommend there solution question,more efficently ,can give me advice,thank in advance

i came across same problem recently. make clear:

problem statement

you given sequence of integers a1,a2,a3.....an. free replace integer other positive integer. how many integers must replaced make resulting sequence strictly increasing?

input format

the first line of test case contains integer n - number of entries in sequence. next line contains n space separated integers ith integer ai.

output format

output minimal number of integers should replaced make sequence strictly increasing.

given input, len = 5, arr = [1 2 2 3 4], after minus index+1, [0 0 -1 -1 -1].

ignoring negative elements(these must changed), compute longest increasing subsequence(nondecreasing problem), classic dynamic programming problem.

denote length of lis = n(these elements not changed). final answer(the part doesn't belong increasing subsequence , ignored negative part) len-n(5-2=3).

we can compute lis in o(nlogn) time o(n) space.

int solve(vector<int> &arr) {     int len = arr.size();     for(int = 0; < len; i++) {         arr[i] -= i+1;     }     vector<int> lis(len,0);     int n = 0;     for(int = 0; < len; i++) {         if(arr[i] >= 0) {             int pos = binarysearchpos(lis,n,arr[i]);             lis[pos] = arr[i];             if(n == pos)                 n++;         }     }     return len-n; }  int binarysearchpos(vector<int> &arr, int n, int target) {     if(n == 0)         return 0;     if(arr[n-1] <= target)         return n;     int low = 0, high = n-1;     while(low < high) {         int mid = (low+high)/2;         if(arr[mid] > target) {             high = mid;         } else {             low = mid+1;         }     }     return low; }