# problem finding the longest increasing sequence in 2-D array

Page 1 of 1

## 0 Replies - 2333 Views - Last Post: 05 October 2012 - 10:43 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294419&amp;s=fab70c18eb24dfe4dcec2889b601d59a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 butterfly13

Reputation: 0
• Posts: 1
• Joined: 05-October 12

# problem finding the longest increasing sequence in 2-D array

Posted 05 October 2012 - 10:43 AM

In this program the purpose is to find the longest increasing subsequence in a two-dimensional array using recursion, and. The input file is being read and the input is being placed in a ArrayList<String>.

I'm having problems checking the boundaries across the Map, since I have to check the top, bottom , left, right, and the top-left, top-right, bottom-left, bottom-right.

For my private getLongestSequence the idea is to

// Private recursive routine
ArrayList getLongestSequence( Position startingSquare )
{
ArrayList result = new ArrayList( );

for each Position p that is adjacent to startingSquare AND has a large value )
{
recursively compute the longest sequence starting at p
and if this sequence is longer than the one in result,
update result
}

return result;
}

```import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

public class Main
{
private static ArrayList<String> list = new ArrayList();
private static Map<Location, ArrayList<Location>> m = new HashMap();
private static int column, rows;

public static void main(String[] args) throws FileNotFoundException
{
File f = new File("numbers1.txt");
Scanner scanner = new Scanner(f);  //reads the file

while(scanner.hasNextLine())    //while the file has next line, add the string to the list
{
}
column = (new StringTokenizer(list.get(0))).countTokens(); //count the columns
rows = list.size();  //count the rows
ArrayList <Location> newList = makeArray(list); //create an arrayList
//with the Location of each token
//   ArrayList<Location> test = getLongestSequence2(newList.get(22));
}
public ArrayList getLongestSequence(ArrayList<Location> l)
{
for (Location loc: l)
m.put(loc,getLongestSequence2(loc));

Map.Entry<Location, ArrayList<Location>> maxEntry = null;

for(Map.Entry<Location, ArrayList<Location>> entry : m.entrySet())
{
if (maxEntry == null || entry.getValue().size() > maxEntry.getValue().size())
maxEntry = entry;
}
return maxEntry.getValue();
}

// I have trouble checking for the boundaries to implement the recursion,

private static ArrayList<Location> getLongestSequence2(Location startL)
{
ArrayList<Location> result = new ArrayList();

m.get(new Location (startL.getRow()-1,startL.getCol()-1,startL.getValue()));
System.out.println("RRRRRRR " + startL);

return result;
}

private boolean boundaries(int row, int col)
{
if((row>=0 && row< rows)&& (col>=0 && col<column))
return true;
return false;
}
private static ArrayList<Location> makeArray(ArrayList<String> l)
{
ArrayList<Location> arr =new ArrayList();
StringTokenizer string ;
Location loc;
int c;
for(int i=0; i<l.size(); i++)
{
string = new  StringTokenizer(l.get(i));
c = 0;
while(string.hasMoreTokens())
{
loc = new Location(i,c,Integer.parseInt(string.nextToken()));
c++;

}
}

return arr;
}
public Location checkBoundaries(Location square, int direction)
{
switch(direction)
{
case 0: return square.
}
return null;
}
}

```

This is the Location Class

```public class Location
{
private int row, col, values;
public Location(int r, int c,int v )
{
row = r;
col = c;
values = v;
}
public int getValue()
{
return values;
}
public int getRow()
{
return row;
}
public int getCol()
{
return col;
}

public String toString()
{
return row+"," + col;
}
}

```

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul{list-style-type:circle;font-size:12px;font-weight:bold;}.related li{margin-bottom:5px;background-position:left 7px!important;margin-left:-35px;}.related h2{font-size:18px;font-weight:bold;}.related a{color:blue;}