Minimum Sum of the given array.

You have given an array of Integer. You can change the sign of any element of the array. Write a program-me to find minimum sum of the given array.
For Example: 2 1 3 4 2
Minimum sum = 0 if -2, -1, -3 , 4,  2
Approach: Problem can be reduced to dividing a sequence of integers into two sets such that the sum of the digits in one set is equal to the sum of the digits in the other set.

public class MinimumSum {

	public static boolean calculate(int arr[], int tot, int totalSum)
	{
	    int n = arr.length;
		boolean dp[][] = new boolean[totalSum+1][n+1];
	    if(dp[tot][n-1] == false)
	    {
	       for(int i = 0; i < n; i++)
	         dp[arr[i]][i] = true;
	       
	 
	       int sum = arr[0];
	       for(int k = 1; k < n; k++)
	       {
	          sum += arr[k];
	          int lim = tot < sum ? tot : sum;
	          for(int i = 1; i <=lim; i++)
	          {
	              dp[i][k] |= dp[i][k-1];
	              if(i > arr[k])
	                  dp[i][k] |= dp[i-arr[k]][k-1];
	          }
	       }
	    }
	    
	    return dp[tot][n-1];
	}
	 
	public static int solve(int arr[])
	{
		int n = arr.length;
	    int tot = 0;
	    if (n == 1)
	       return arr[0];
	 
	    for(int i = 0; i < n; i++)
	    {
	       tot += arr[i];
	    }
	    
	     
	    int min_sum = Integer.MAX_VALUE;
	    for(int i = 1; i <= tot/2; i++)
	    {
	       boolean temp1, temp2;
	      
	       temp1 = calculate(arr, i,tot);
	       temp2 = calculate(arr, tot - i,tot);
	       
	       if((temp1 == true) && (temp2 == true))
	       {
	          if(min_sum  > (tot-i-i))
	             min_sum = tot - i - i;           
	          
	       }
	   }        
	   return min_sum;
	}
	 
	public static void main(String[] args) {
		int arr[] = {2,1,3,4,2};
		System.out.println("elements min sum"+solve(arr));

	}

}

Longest Increasing and Decreasing Subsequence problem

You have a sequence of numbers from which you must create the longest subsequence satisfying the following condition: it can be 'cut' into two parts that share exactly one common element (the last element of the first part is the first element of the second part), and the first part is sorted in strictly ascending order while the second part is sorted in strictly descending order. For example, the sequence { 1, 4, 6, 5, 2, 1 } can be 'cut' into { 1, 4, 6 } and { 6, 5, 2, 1 }. The two parts share the 6, and the first sequence is sorted in ascending order while the second sequence is sorted in descending order.
You are given a int[] numbers, a sequence of numbers. Return the minimal number of elements you must throw out from the given sequence such that the remaining subsequence satisfies the condition described above.

0)
{1, 4, 6, 5, 2, 1}
Returns: 0
This sequence already satisfies the condition, so the answer is 0.
1)
{1, 2, 1, 2, 3, 2, 1, 2, 1}
Returns: 4
The longest subsequence is { 1, 2, 3, 2, 1 }, so you need to throw out at least 4 elements.
2)
{2, 2, 2, 2, 2}
Returns: 4
3)
{4,5,65,34,786,45678,987,543,2,6,98,580,4326,754,54,2,1,3,5,6,8,765,43,3,54}
Returns: 14

http://community.topcoder.com/stat?c=problem_statement&pm=5922

public class IncreasingDecreasingSubseq {

	
	public static void findMinimumCuts(int arr[])
	{
		
		int size = arr.length;
		int lis[] = new int[size];
		int lds[] = new int[size];
		// Longest Increasing sequence
		   for(int i = 0; i < size; ++i)
		   {
		       for(int j = 0; j < i; ++j)
		       {
		           if(arr[j] < arr[i])
		           {
		               lis[i] = Math.max(lis[j] + 1, lis[i]);
		           }
		       }
		   }
		   
		   // Longest decreasing sequence
		   for(int i = size - 1; i >= 0; --i)
		   {
		      for(int j = size - 1; j > i; --j)
		      {
		          if(arr[j] < arr[i])
		          {
		             lds[i] = Math.max(lds[j] + 1, lds[i]);
		          }
		      }
		   }
		   
		   int best = 0;
		   for(int i = 0; i < size; ++i)
		   {
		      best = Math.max(best, lds[i] + lis[i]);
		   }
		   System.out.println("Best"+best);
		   System.out.println("Number to be removed : " + (size - best - 1));
		
	}
	
	public static void main(String[] args) {

		int a[] = {1, 2, 1, 2, 3, 2, 1, 2, 1};
		int b[] = {4,5,65,34,786,45678,987,543,2,6,98,580,4326,754,54,2,1,3,5,6,8,765,43,3,54};
		findMinimumCuts(a);
		findMinimumCuts(b);
	}

}

Maximal Increasing subsequence

A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.
For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.
You will be given a as an int[] representing a sequence of distinct numbers. Return the number of maximal increasing subsequences it contains

http://community.topcoder.com/stat?c=problem_statement&pm=7753

public class MaximalIncreasinSubsequence {

	public static long findMaximalIncreasingSubsequence(int arr[]) {
		int size = arr.length;
		int end[] = new int[size];
		end[0] = 1;

		for (int i = 1; i < size; i++) {
			int shadow = 0;
			int sum = 0;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] > shadow && arr[j] < arr[i]) {
					shadow = arr[j];
					sum = sum + end[j];
				}
			}
			if (sum == 0)
				sum = 1;
			end[i] = sum;
		}
		long finalanswer = 0;

		int max = 0;
		for (int i = size - 1; i >= 0; i--) {
			if (max < arr[i]) {
				finalanswer = finalanswer + end[i];
				max = arr[i];
			}
		}
		return finalanswer;
	}

	public static void main(String[] args) {
		
		int arr[] = {1,3,2,6,4,5};
		int b[] = {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2};
		System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(arr));
		System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(b));

	}

}

Three product

Given a set of positive integers s = {a1, a2, ..., an},
There exists ai * aj = ak,  i != j != k
Find the maximum number satisfying the above conditions, if there are no three numbers satisfying the above condition, the output –1

public static int findProduct(int a[]) {
		int n = a.length;

		for (int i = 0; i < n; i++) {
			for (int j = 0, k = i + 1; j < i && k < n;) {
				if (a[i] * a[j] == a[k]) {
					return a[k]; // find
				} else if (a[i] * a[j] > a[k])
					k++;
				else
					j++;
			}
		}

		return -1;
	}

Insertion Sort Variant

Problem Statement

We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.

For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.

You will be given a int[] theArray. Return the minimal total cost required to sort the array.

http://community.topcoder.com/stat?c=problem_statement&pm=4844

public class MinimalCostSort {

	public static int calcMinimalCost(int[] arr) {
		int[] f = new int[arr.length];
		int res = 0;
		for (int i = 0; i < arr.length; i++) {
			f[i] = arr[i];
			for (int j = 0; j < i; j++) {
				if (arr[j] <= arr[i])
					f[i] = Math.max(f[i], f[j] + arr[i]);
			}
			res = Math.max(res, f[i]);
		}
		res = -res;
		for (int i = 0; i < arr.length; i++)
			res += arr[i];
		return res;
	}

	public static void main(String[] args) {

		int a[] = {6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2};
		int b[] = {8, 2, 6, 5, 1, 4};

		System.out.println("Minimal cost is "+calcMinimalCost(a));
		System.out.println("Minimal cost is "+calcMinimalCost(b));
	}

}