Upsolved Weekly Contest 132

varunu28 · varunu28 · commit fc1c43f3a74e · 2019-04-14T15:14:22.000-07:00
diff --git a/Contests/Weekly Contest 132/Divisor Game.java b/Contests/Weekly Contest 132/Divisor Game.java
@@ -0,0 +1,5 @@
+class Solution {
+    public boolean divisorGame(int N) {
+        return N % 2 == 0;
+    }
+}
diff --git a/Contests/Weekly Contest 132/Longest Arithmetic Sequence.java b/Contests/Weekly Contest 132/Longest Arithmetic Sequence.java
@@ -0,0 +1,35 @@
+class Solution {
+    public int longestArithSeqLength(int[] A) {
+        if (A.length <= 1) {
+            return A.length;
+        }
+        
+        int res = 0;
+        HashMap<Integer, Integer>[] dp = new HashMap[A.length];
+        
+        for (int i = 0; i < A.length; i++) {
+            dp[i] = new HashMap<>();
+        }
+        
+        for (int i = 1; i < A.length; i++) {
+            int curr = A[i];
+            for (int j = 0; j < i; j++) {
+                int prev = A[j];
+                int diff = curr - prev;
+                
+                int len = 2;
+                
+                if (dp[j].containsKey(diff)) {
+                    len = dp[j].get(diff) + 1;
+                }
+                
+                int currLen = dp[i].getOrDefault(diff, 0);
+                dp[i].put(diff, Math.max(currLen, len));
+                
+                res = Math.max(res, dp[i].get(diff));
+            }
+        }
+        
+        return res;
+    }
+}
diff --git a/Contests/Weekly Contest 132/Maximum Difference Between Node and Ancestor.java b/Contests/Weekly Contest 132/Maximum Difference Between Node and Ancestor.java
@@ -0,0 +1,29 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public int maxAncestorDiff(TreeNode root) {
+        return dfs(root, root.val, root.val);
+    }
+    
+    public int dfs(TreeNode root, int min, int max) {
+        if (root == null) {
+            return 0;
+        }
+        
+        int res = Math.max(max - root.val, root.val - min);
+        max = Math.max(root.val, max);
+        min = Math.min(root.val, min);
+        
+        res = Math.max(res, dfs(root.left, min, max));
+        res = Math.max(res, dfs(root.right, min, max));
+        
+        return res;
+    }
+}
