Find the length of the longest subsequence of a given sequence

int lis( int arr[], int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
 
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
    
   /* Compute optimized LIS values in bottom up manner */
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
    
   // To get Max element in lis[]
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];
 
   free( lis );
 
   return max;
}

Test case

{ 10, 22,  9, 33}

 i=1 j=0 
 lis[1] = 2
 
 i=2 j=0     i=2 j=1
 no change
 
 i=3 j=0     i=3 j=1     i=3 j=2
 lis[3] =2   lis[3] =3   
 
 max = 3

Reverse string without using temporary variable or reverse() function

String s = "Hello World!";
for(int i = 0; i < s.length(); i++)
{
    s = s.substring(1, s.length() - i) + s.charAt(0) + s.substring(s.length() - i);
}
System.out.println(s);

OR

String str = "Hello World!";

int len = str.length();
for (int i = (len-1); i >= 0; --i) 
    str += str.charAt(i);
str = str.substring(len);

System.out.println(str);

Find day of the week for a given date

int dayofweek(int d, int m, int y)
{
    static int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
    y -= m < 3;      // m < 3 is either 1 or 0 
                                                  // So y=y-1 when m<3 or y=y-0 when m>=3
    return ( y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

Explanation
Assume now that leap years did not exist and every year had 365 days.

Knowing what day January 1 falls on a certain year, it is easy to find which  day any other date falls. January has 31 =  7 × 4 + 3 days, so February 1 will fall on the day which follows three  days after January 1. Similarly, March 1 will fall on the day three days  after the day corresponding to January 1, April 1 will fall 6 days  after, and so on. Thus, the first days of each month are offset with  respect to January 1 by the array t[] =  {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}.. Different from the original t[] given in the question is due to leap years which will be explained later.

Since 365 = 7 × 52 + 1, the day corresponding to a given date will become  incremented by 1 every year. For example, July 14, 2014 is a Monday and  July 14, 2015 will be a Tuesday. Hence adding the difference between year numbers allows us to switch from the day of a reference year to any other year.

At this stage, the leap-year free dow function can be written as such:

int dow(int y, int m, int d){ 
  static int t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; 
  return (y + t[m-1] + d) % 7;
}

Considering leap years
Every 4 years,  our calculation will gain one extra day. Except every 100 years when it  doesn’t. Except every 400 years when it does . Just adding  y/4 – y/100 + y/400 works gives exactly the required  number of leap days.

Except one problem. The leap day is not January 0, it is February  29. This means that the current year should not be counted for the leap  day calculation for the first two months.

Suppose  that if the month were January or February, we subtracted 1 from the  year. This means that during these months, the y/4 value would be that of the previous year and would not be counted.

Except for a tiny problem. We are subtracting 1 from the year for January and February for non-leap years too. This means that there would be a “blank” day between February 28 and March 1, that is, we have made every non-leap year a leap year, and leap years double-leap years. So we subtracted 1 from the t[] values of every month after  February? That would fill the gap, and the leap year problem is solved.  That is, we need to make the following changes:
•    t[] now becomes {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}
•    if m corresponds to Jan/Feb (that is, m<3) we decrement y by 1
•    the annual increment inside the modulus is now y + y/4 – y/100 + y/400 in place of y