(UVA) Murcia's Skyline - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=142&problem=2890&mosmsg=Submission+received+with+ID+17387432

The problem wants us to determine if the length of the longest subsequence is increasing or decreasing, and it also wants the longest length of both subsequence. Then, the solution below used Dynamic Programming to solve this problem, applying the concept of the Longest Increasing Subsequence.




import java.io.*;
import java.util.*;

class Main {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numTests = Integer.parseInt(br.readLine());
        for (int i = 0; i < numTests; i++) {
            int numBuildings = Integer.parseInt(br.readLine());

            String line = br.readLine();
            String[] s = line.split("\\s");
            int[] height = new int[numBuildings];
            for (int j = 0; j < numBuildings; j++) {
                height[j] = Integer.parseInt(s[j]);
            }
            line = br.readLine();
            s = line.split("\\s");
            int[] width = new int[numBuildings];
            for (int j = 0; j < numBuildings; j++) {
                width[j] = Integer.parseInt(s[j]);
            }
           
            Building[] buildings = new Building[numBuildings];
            for (int j = 0; j < numBuildings; j++) {
                buildings[j] = new Building(height[j], width[j], width[j]);
            }
           
            for (int j = numBuildings-1; j >= 0; j--) {
                int maxLengthIncr = buildings[j].lengthIncr;
                int maxLengthDecr = buildings[j].lengthDecr;
                for (int k = j+1; k < numBuildings; k++) {
                    if (buildings[j].height < buildings[k].height) {
                        int length = buildings[j].lengthIncr + buildings[k].lengthIncr;
                        if (length > maxLengthIncr) {
                            maxLengthIncr = length;
                        }         
                    }
                    else if (buildings[j].height > buildings[k].height) {
                        int length = buildings[j].lengthDecr + buildings[k].lengthDecr;
                        if (length > maxLengthDecr) {
                            maxLengthDecr = length;
                        }
                    }
                }
                buildings[j].lengthIncr = maxLengthIncr;
                buildings[j].lengthDecr = maxLengthDecr;
            }
           
            int maxDec = -1;
            int maxInc = -1;
            for (int j = 0; j < numBuildings; j++) {
                maxDec = Math.max(maxDec, buildings[j].lengthDecr);
                maxInc = Math.max(maxInc, buildings[j].lengthIncr);
            }
           
            if (maxInc >= maxDec) {
                System.out.println("Case " + (i+1) + ". Increasing (" + maxInc + "). Decreasing (" + maxDec + ").");
            }
            else {
                System.out.println("Case " + (i+1) + ". Decreasing (" + maxDec + "). Increasing (" + maxInc + ").");
            }
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Building {
    int height;
    int lengthIncr;
    int lengthDecr;
   
    public Building(int h, int lI, int lD) {
        height = h;
        lengthIncr = lI;
        lengthDecr = lD;
    }
}