Cut The Rope

Problem:

Given a integer n, find all the subsets of n such that product obtained is maximum.

Eg 1: n = 10 {3 ,3 ,4} gives us 36 (highest product)

Eg 2: n = 20 {3 ,2 ,3 ,4 ,5 ,3} gives us 1080 (highest product)

Background:

At first glance i saw this problem as a inverted sum of subset problem, where we have given subsets as well as sum, but it is inverted because here we have just sum (n here) no subsets , we have to find all the subsets as a part of the solution.

After finding 1st subset store it somewhere, find next, now compare 1st and 2nd subsets product,

if 2nd subset-product > 1st subset-product

   store 2nd subset-product in some variable

repeat it until loops are exhausted.

Instead of solving it recursively i tried to solve it with tight for loops and a while loop.

Time Complexity:

O(n^2) and additional O(n) extra space.

Code:

import java.util.ArrayList;

public class CutTheRope {

 private int val;
 private int highval;
 private int m;
 /**
  * @param n
  */
 void start( int n ) {
  
  for (int i = 2; i < n-1; i++) {
   ArrayList myList = new ArrayList();
   myList.add(i);
   boolean isTrue = false;
   while (!isTrue) {
    
    
    for (int j = 2; j < n-1; j++) {
     int k = 0;
     for (Integer integer : myList) {
      k += integer.intValue();
     }
     //k+j+1 should not be equal to n ...
                                        //bcoz we r not staring loop from 1 its from 2
     if(k+j <= n && (k+j+1) != n)
      myList.add(j);
     if(k+j==n) {
      isTrue = true;
      break;
     }
    }
   }
   for (Integer integer : myList) {
    val = mult(integer.intValue());
    //System.out.print(integer + " ,");
   }
   //System.out.println();
   
   if (m >= 1) {
    if (highval < val)
     highval = val;
   }else {
   m++;
   highval = val;
   }
   k = -1;
  }
  if(highval != 0)
 System.out.println(highval);
   else
 System.out.println(n);
 }
 
 int k =-1;
 private int mult(int intValue) {
  // TODO Auto-generated method stub
  if(k == -1) {
   k = intValue;
  }
  else
  {
   k *= intValue;
  }
  return k;
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new CutTheRope().start(22);
 }

}

Try it!

Good Luck.......