## 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++) { ArrayListTry it!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); } }

Good Luck.......