ShiguangWang
BAN USERArrayList<String> pairs(int n){
return pairs(n, n, "");
}
ArrayList<String> pairs(int open, int close, String s){
ArrayList<String> ret = new ArrayList<String>();
if(open == 0){
for(int i = 0; i<close; i++){
s += ")";
}
ret.add(s);
} else{
ret.addAll(pairs(open-1, close, s+"(");
if(close > open){
ret.addAll(pairs(open, close-1, s+")");
}
}
return ret;
}
String neg2base(int x){
String ret = "";
int remains = 0;
while(Math.abs(x) != 0){
remains = x%2 == 0?0:1;
x -= remains;
x /= -2;
ret = remains + ret;
}
return remains + ret;
}
This algorithm will give the consecutive sub-array with the two properties. But in a general case where the sub-array needs not to be consecutive, the algorithm will not give the optimal solution.
This problem is a weighted version of the longest increasing subsequence problem. I give a O(n^2) algorithm below:
double max_sum(List pairs){
pairs = pairs.leftappend(<Integer.MinValue, 0>);
int n = pairs.length;
double[][] L = new double[n][n];
for(int i = 0; i<n; i++){
if(pairs[i].a >= pairs[n-1].a){
L[i][n-1] = Integer.MinValue;
} else {
L[i][n-1] = pairs[n-1].b;
}
}
for(int j = n-2; j>= 0;j--){
for(int i = 0; i<n; i++){
L[i][j] = L[i][j+1];
if(pairs[i].a < pairs[j].a){
if(L[i][j] < L[j][j+1] + pairs[j].b){
L[i][j] = L[j][j+1] + pairs[j].b;
}
}
}
}
return L[0][1];
}
Please note that the solution above assumes the linear function is ax+by = c, therefore the distance function is |ax1 + by1 -c| / sort(a^2 + b^2).
Since sqrt(a^2+b^2) will be appear for each (xi, yi), we do not need to calculate it when doing comparisons.
Therefore, the objective function is actually to minimize (axi+byi+c)^2 assuming the linear function in the form ax + by = c.
int rand(int N, int[] K){
int R = N - K.length;
Random rand = new Random();
int p = rand.nextInt(R);
int j = 0;
int ret = 0;
for(;j<K.length; j++){
if(ret == K[j])
ret ++;
else
break;
}
for(int i = 0; i<p; i++){
if(j < K.length && ret == K[j]){
j++;
ret ++;
}
ret ++;
}
return ret;
}
void reconstructRoute(Ticket[] tickets, Place curLocation){
HashMap<Place, ArrayList<Ticket>> map = new HashMap<Place, ArrayList<Ticket>>();
for(Ticket t : tickets){
Place begin = t.from;
Place end = t.to;
ArrayList<Ticket> arr;
if(map.hasKey(begin)){
arr = map.get(begin);
}
else {
arr = new ArrayList<Ticket>();
}
arr.add(t);
map.put(begin, arr);
if(map.hasKey(end)){
arr = map.get(end);
}
else{
arr = new ArrayList<Ticket>();
}
arr.add(t);
map.put(end, arr);
}
ArrayList<Place> route = new ArrayList<Place>();
Place c = curLocation;
for(int i = 0; i<tickets.length; i++){
Ticket t = map.get(c);
route.add(c);
c = t.from;
}
route.add(c);
for(int i = route.size()-1; i>=0; i--){
System.out.println(route.get(i));
}
}
boolean SubSetSum(int[] S, int target){
// I assume that all the integers in S and the target is positive
boolean[] A = new int[target];
for(int i = 0; i<target; i++){
int value = false;
for(int j = 0; j<S.length; j++){
if(S[j] == i+1){
value = true;
break;
}
else if(i+1 - S[j]> 0 && A[i+1-S[j]]){
value = true;
break;
}
}
A[i] = value;
}
return A[target-1];
}
- ShiguangWang December 03, 2013