CareerCup

Could you explain the problem a bit more please? Is each vacation in the int[48] array a number between 1-7 (vacation days for that week)?

We could simply create a 2D matrix with rows = city, columns = weeks (so 48 columns). Go through each column and pick the max from that column. Now just visit the cities at these max-vacation points for all 48 weeks.

Yes , Each vacation in the array is a number between 1 and 7 . You are right about going though each row column and pick the max .

Second part is , now assume not all cities are connected , then how would do it ?

I would ask for adjacency list and do a DFS on it, counting total vacation count, increasing week counter.
When I hit week 48, check if current route is most optimal

I believe this is variation of traveling salesman problem (graphs)

This looks like a min. cost max flow problem.

package helloworld;

import java.util.HashMap;

public class TopTrip{
	private static int TOTAL_WEEKS = 4 - 1; // start counting from zero

	private int getLongestVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek){
		int maxVac = -1;
		for(Integer currcity : vacations.keySet()){
			int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
			if(currCityVal > maxVac){
				maxVac = currCityVal;
			}
		}
		return maxVac;
}
private int getCityVacationAtWeek(HashMap<Integer, Integer[]> vacations, int startWeek, int city){
		Integer[] cityVacs = vacations.get(city);
		return cityVacs[startWeek];
}
	private int calculateBestPath(HashMap<Integer, Integer[]> vacations, int startWeek, Integer[] visitedCities){
		if(startWeek == TOTAL_WEEKS){
			Integer city = new Integer(-1);
			Integer longest = getLongestVacationAtWeek(vacations, startWeek);
			int maxVac = -1;
			for(Integer currcity : vacations.keySet()){
				int currCityVal = getCityVacationAtWeek(vacations, startWeek, currcity);
				if(currCityVal > maxVac){
					maxVac = currCityVal;
					city = currcity;
				}
			}
			visitedCities[startWeek] = city;
			return longest;
		}
		int longestTripInTotal = 0;
		for(int city : vacations.keySet()){
			
			int cityVacationAtWeek = getCityVacationAtWeek(vacations, startWeek, city);
			int longestVacationFromCity = cityVacationAtWeek + calculateBestPath(vacations, startWeek+1,visitedCities);
			if(longestVacationFromCity > longestTripInTotal){
				visitedCities[startWeek] = city;
				longestTripInTotal = longestVacationFromCity;
			}
		}
		return longestTripInTotal;
	}
	public Integer[] getTopTrip(HashMap<Integer, Integer[]> vacations){
		Integer[] result = null;

		if(vacations == null){
			return result;
		}
		if(vacations.keySet().size() == 0){
			return result;
		}
		result = new Integer[TOTAL_WEEKS+1];
		int longestPath = calculateBestPath(vacations, 0, result);
		System.out.println("The longest trip is:" + longestPath);
		return result;
	}
	public static void main(String[] args){
	TopTrip tv = new TopTrip();
	Integer[] city0 = {1,1,2,11};
	Integer[] city1 = {5,1,3,7};
	Integer[] city2 = {1,1,4,13};
	HashMap<Integer, Integer[]> v = new HashMap<Integer, Integer[]>();
	v.put(0,city0);
	v.put(1,city1);
	v.put(2,city2);
	Integer[] path = tv.getTopTrip(v);
	for(Integer i : path){
		System.out.print(i + "->");
	}
}
}