c - A better approach for the following (better time complexity) than the recursion I have used -

there n balls each particular weight , cost. balls have removed such cost of balls removed maximum. additional condition sum of weights of last k balls should <= weight of the remaining balls multiplied constant q (k constant: given). balls can removed ends. how can cost maximised. can solve question using recursive algorithm. know how reduce complexity o(n) using queues.

 #include<stdio.h>  long int q, val[100000], wt[100000],k,n;  long int steal(long int l,long int r,long int cut) {     long int i,sum,steal1, steal2 ,x, y = 0;     for(i = r; > r - k; i--)         y = y + wt[i];     sum = 0;     for(i = l; <= r; i++)         sum = sum + wt[i];     x = sum - y;     if(x * q < y)         return 0;     else     {         steal1 = steal(l, r-1, r);         steal2 = steal(l+1, r, l);         if(steal1 == 0 && steal2 != 0)             return steal2 ;         else if(steal1 != 0 && steal2 == 0)             return steal1 ;         else if(steal1 == 0 && steal2 == 0)         {             if(r-l+1 == n)                 return 0;             else                  return val[cut];         }         else         {             if(steal1+val[r] > steal2+val[l])                 return steal1+val[r];             else                  return steal2+val[l];         }     } }  int main() {     long int i;     scanf("%ld %ld %ld", &n, &k, &q);     for(i = 0; < n; i++)         scanf("%ld", &wt[i]);     for(i = 0; < n; i++)         scanf("%ld", &val[i]);     printf("%ld\n", steal(0, n - 1,n));     return 0; } 

test case : 5 2 1 (n, k , q respectively) 5 4 6 3 2 (weights of n balls) 3 2 4 2 2 (value of each ball)

answer : 5

things fixed:

1. you have arrays declared 100000 elements, regardless of actual value of n, should size instead. if 100000 < n, arrays small , have problems due index out of bounds. if n < 100000, waste lot of memory. instead of initializing arrays 100000 element, initialize them n elements. read this further info.
2. you use insertion sort while reading input, sort elements weight, value, or formula, able differentiate balls weight, or value, or formula suits needs better.
3. with recursion using stack. use custom stack purpose.
4. if want queue balls, queue can 1 created @ 2.
5. if want best solution, need implement divide et impera purpose.