I try to solve a Longest Anchored Comb Problem by dynamic programming but do not know how to achieve the algorithm. Codes except the algorithm have been written down below.
Can someone tell me how to solve the algorithm part?
Here are the definition of the problem.
In the list of numbers, any subsequence in this array of the form A[i1], A[i1 + 1], A[i2], A[i2 + 1], . . . , A[ik], A[ik + 1] of 2k elements of array A, for some integer k ≥ 1, and for some indices 1 ≤ i1 < i1 + 1 < i2 < i2 + 1 < · · · < ik < ik + 1 ≤ n such that A[i1] < A[i1 + 1] > A[i2] < A[i2 + 1] > A[i3] < · · · > A[ik] < A[ik + 1], is called a comb.
We call a given comb A[i1], A[i1 + 1], A[i2], A[i2 + 1], . . . , A[ik], A[ik + 1] anchored if A[i1] = A[ik] .
3 examples:
For instance if A[1, 3, 10, 15, 21], n = 5, then because this sequence is increasing, the longest comb has length k = 1, and such longest comb is not unique, e.g., 1, 3; 3, 10; 15, 21 – are examples of 3 longest and anchored combs, each of length 1, i.e., each having one tooth. The output in this instance is therefore 1. Another example of the input array A = [5, 3, 2, 1] with n = 4, where the sequence is decreasing means that there is no comb there, so the output to the Longest Anchored Comb Problem is 0.
Another input A[1, 3, 2, 11, 12, 10, 11, 2, 23] with n = 9. Here subsequence A[1], A[2], A[3], A[4], A[6], A[7], A[8], A[9], which is 1, 3, 2, 11, 10, 11, 2, 23,is a comb of length k = 4 (with 4 teeth), but it is not anchored because the first elements of its first and last teeth are not equal: A[1] = 1 and A[8] = 2. However, subsequence A[3], A[4], A[6], A[7], A[8], A[9] which is 2, 11, 10, 11, 2, 23 is an anchored comb of length k = 3 (with 3 teeth), because the first elements of its first and last teeth are equal: A[3] = 2 and A[8] = 2. This is also the longest anchored comb in this instance, so the output to the Longest Anchored Comb problem is 3.
3.Suppose, for instance, that n = 10 and that the input sequence is: 1 3 2 4 3 5 4 6 1 3, that is, A[1] = 1, A[2] = 3, A[3] = 2, A[4] = 4, A[5] = 3, A[6] = 5, A[7] = 4, A[8] = 6, A[9] = 1, A[10] = 3. Then, for instance, A[2] = 3, A[4] = 4, A[5] = 3, A[6] = 5 is an anchored comb of length 2, but the longest anchored comb is the whole array and has length 5.
import javax.xml.crypto.Data;
import java.io.File;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
public static ArrayList<String> ReadData(String pathname) {
ArrayList<String> strlist = new ArrayList<String>();
try {
File filename = new File(pathname);
InputStreamReader reader = new InputStreamReader(
new FileInputStream(filename));
BufferedReader br = new BufferedReader(reader);
int j = 0;
String line = "";
while ((line = br.readLine()) != null) {
strlist.add(line);
}
return strlist;
} catch (Exception e) {
e.printStackTrace();
}
return strlist;
}
public static ArrayList<ArrayList<Integer> > DataWash(ArrayList<String> Datalist) {
ArrayList<ArrayList<Integer> > AIS = new ArrayList<ArrayList<Integer> >();
ArrayList<Integer> IS = new ArrayList<Integer>();
for (int i = 0; i < Datalist.size(); i++) {
String Tstr = Datalist.get(i);
if (Tstr.equals("A") == false) {
IS.add(Integer.parseInt(Tstr));
}
if (Tstr.equals("A")) {
ArrayList<Integer> elemAIS = new ArrayList<Integer>(IS);
AIS.add(elemAIS);
IS.clear();
}
}
return AIS;
}
//%%%%%%%%%%%%%%%%%%%%%%% Procedure LongestComb() that contains code to write.
//These codes are to complete:
public static int LongestComb(int[] A, int n){
/* Input is array of input sequence (a_1 <= a_2 <= ... <= a_n) as A[0,1,...,n-1], that is,
a_1 = A[0], a_2 = A[1], ..., a_n = A[n-1].
n = number of integers in sequence A
This procedure returns the value of the longest anchored comb (>= 1) or 0 if there is no anchored comb. It should not return the respective anchored comb.
*/
/*
Given an array T[1,...,n]
then M = max_{k: some condition C(k) holds} [ T[k] ],
M denotes the largest value T[k] over all indices k such that condition C(k) holds.
.....
.....
*/
/* Here should be the statement and description of the running time
analysis: describe how the running time depends on
n (length of the input sequence), and give short argument.
.....
.....
*/
/* Here should be the code to solve the problem:
.....
.....
return ...;
*/
} // end of procedure LongestComb()
public static int Computation(ArrayList<Integer> Instance, int opt){
// opt=1 here means option 1 as in -opt1, and opt=2 means option 2 as in -opt2
int NGounp = 0;
int size = 0;
int Correct = 0;
size = Instance.size();
int [] A = new int[size-opt];
// NGounp = Integer.parseInt((String)Instance.get(0));
NGounp = Instance.get(0); // NOTE: NGounp = 0 always, as it is NOT used for any purpose
// It is just the first "0" in the first line before instance starts.
for (int i = opt; i< size;i++ ){
A[i-opt] = Instance.get(i);
}
int Size =A.length;
if (NGounp >Size ){
return (-1);
}
else {
//Size
int R = LongestComb(A,Size);
return(R);
}
}
public static String Test;
public static void main(String[] args) {
if (args.length == 0) {
String msg = "Rerun with flag: " +
"\n\t -opt1 to get input from dataOne.txt " +
"\n\t -opt2 to check results in dataTwo.txt";
System.out.println(msg);
return;
}
Test = args[0];
int opt = 2;
String pathname = "dataTwo.txt";
if (Test.equals("-opt1")) {
opt = 1;
pathname = "dataOne.txt";
}
ArrayList<String> Datalist = new ArrayList<String>();
Datalist = ReadData(pathname);
ArrayList<ArrayList<Integer> > AIS = DataWash(Datalist);
int Nins = AIS.size();
int NGounp = 0;
int size = 0;
if (Test.equals("-opt1")) {
for (int t = 0; t < Nins; t++) {
int Correct = 0;
int Result = 0;
ArrayList<Integer> Instance = AIS.get(t);
Result = Computation(Instance, opt);
System.out.println(Result);
}
}
else {
int wrong_no = 0;
int Correct = 0;
int Result = 0;
ArrayList<Integer> Wrong = new ArrayList<Integer>();
for (int t = 0; t < Nins; t++) {
ArrayList<Integer> Instance = AIS.get(t);
Result = Computation(Instance, opt);
System.out.println(Result);
Correct = Instance.get(1);
if (Correct != Result) {
Wrong.add(t+1);
wrong_no=wrong_no+1;
}
}
if (Wrong.size() > 0) {System.out.println("Index of wrong instance(s):");}
for (int j = 0; j < Wrong.size(); j++) {
System.out.print(Wrong.get(j));
System.out.print(",");
/*ArrayList Instance = (ArrayList)Wrong.get(j);
for (int k = 0; k < Instance.size(); k++){
System.out.println(Instance.get(k));
}*/
}
System.out.println("");
System.out.println("Percentage of correct answers:");
System.out.println(((double)(Nins-wrong_no) / (double)Nins)*100);
}
}
}