Longest Increasing Subsequence

for(int i = 1; i < n; i++)
{
    LS[i] = 1;
    for(int j = 0; j <= i; j++)
    {
        if (arr[i] > arr[j] && LS[i]<=LS[j])
            LS[i] = 1 + LS[j];
    }
}

//find max in LS array
return max(LS[]);

How to print maximum number of A’s using given four keys

int findoptimal(int N)
{
    // The optimal string length is N when N is smaller than 7
    if (N <= 6)
        return N;
 
    // Initialize result
    int max = 0;
 
    // TRY ALL POSSIBLE BREAK-POINTS
    // For any keystroke N, we need to loop from N-3 keystrokes
    // back to 1 keystroke to find a breakpoint 'b' after which we
    // will have Ctrl-A, Ctrl-C and then only Ctrl-V all the way.
    int b;
    for (b=N-3; b>=1; b--)
    {
            // If the breakpoint is at b'th keystroke
            int curr = (N-b-1)*findoptimal(b);
            if (curr > max)
                max = curr;
     }
     return max;
}

Explanation
For N = 7
Case1
B = n-3 = 4
AAAA Ctrl-A Ctrl-C Ctrl-V = 8;    n-b-1 = 7-4-1 = 2 * findoptimal(4) = 2*4 = 8

Case2
B = 3
AAA Ctrl-A Ctrl-C Ctrl-V Ctrl-V= 9;  n-b-1 = 7-3-1 = 3* findoptimal(3) = 3*3 = 9

Case3
B = 2
AA Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V =  8; n-b-1 = 7-2-1 = 4* findoptimal(2) = 4*2 = 8

Case4
B = 1
A Ctrl-A Ctrl-C Ctrl-V Ctrl-V Ctrl-V Ctrl-V = 5; n-b-1 = 7-1-1 = 5* findoptimal(1) = 5*1 = 5

For N = 10
B = n-3 = 7

n-b-1 = 10-7-1 = 2*findoptimal(7)

Minimum number of jumps to reach end

/*
 * We use "last" to keep track of the maximum distance that has been reached
 * by using the minimum steps "ret", whereas "curr" is the maximum distance
 * that can be reached by using "ret+1" steps. Thus,
 * curr = max(i+A[i]) where 0 <= i <= last.
 */
    
   int jump(int A[], int n) {
        int ret = 0;
        int last = 0;
        int curr = 0;
        for (int i = 0; i < n; ++i) {
            if (i > last) {
                last = curr;
                ++ret;
            }
            curr = max(curr, i+A[i]);
        }

        return ret;
    }

No. of paths in integer array

An integer array {3,1,2,7,5,6}. One can move forward through the array either each element at a time or can jump a few elements based on the value at that index.

count the number of possible paths to reach the end of the array from start index.

Ex – input {3,1,2,7,5,6}

sol[6] = 1;
for (i = 4; i>=0;i--) {
     sol[i] = sol[i+1];
     if (i+input[i] < 6 && input[i] != 1)
         sol[i] += sol[i+input[i]];             
}

return sol[0];

Print all permutations of a given string

void permute(char *a, int i, int n)   // i = starting index and n = number of       
                                                                  characters
{
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (int j = i; j <= n; j++)
       {
          swap(a[i], a[j]);
          permute(a, i+1, n);
          swap(a[i], a[j]); //backtrack
       }
   }
}

combination to compose n

You can win three kinds of basketball points, 1 point, 2 points, and 3 points. Given a total score n, print out all the combination to compose n

At first position we can have three numbers 1 or 2 or 3.
First put 1 at first position and recursively call for n-1.
Then put 2 at first position and recursively call for n-2.
Then put 3 at first position and recursively call for n-3.

#define MAX_POINT 3
void printArray(int arr[], int arr_size);

void printCompositions(int n, int i)
{
  static int arr[ARR_SIZE];
 
  if (n == 0)
  {
    printArray(arr, i);
  }
  else if(n > 0)
  {
    int k; 
    for (k = 1; k <= MAX_POINT; k++)
    {
      arr[i]= k;
      printCompositions(n-k, i+1);
    }
  }
}