The Fellow Programmer

The demons had captured the princess ( P ) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight ( K ) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons, so the knight loses health ( negative integers) upon entering these rooms; other rooms are either empty ( 0's ) or contain magic orbs that increase the knight's health ( positive integers). In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Write a function to determine the knight's minimum initial health so that he is able to rescue the princess. For example, given the dungeon below, the initial health o

Given a set of distinct positive integers, find the largest subset such that every pair (S i , S j ) of elements in this subset satisfies: S i % S j = 0 or S j % S i = 0. If there are multiple solutions, return any subset is fine. Example 1: Input: [1,2,3] Output: [1,2] (of course, [1,3] will also be ok) Example 2: Input: [1,2,4,8] Output: [1,2,4,8]   class Solution {     public List<Integer> largestDivisibleSubset(int[] nums) {     List<Integer> result = new ArrayList<Integer>();     if(nums==null||nums.length==0)         return result;       Arrays.sort(nums);       int[] arr = new int[nums.length];     int[] index = new int[nums.length];     Arrays.fill(arr, 1);     Arrays.fill(index, -1);       int max=0;     int maxIndex=-1;       for(int i=0; i<arr.length; i++){         for(int j=i-1; j>=0; j--){             if(nums[i]%nums[j]==0 && arr[j]+1>arr[i]){                 arr[i]=arr[j]+1;                 index[i]=j;