fd

dingjikerbo · dingjikerbo · commit d6bf5e79aa85 · 2018-10-30T20:38:52.000+08:00
diff --git a/leetcode/solution/src/LinkedListCycle.java b/leetcode/solution/src/LinkedListCycle.java
@@ -1,9 +1,6 @@
-/**
- * https://leetcode.com/articles/linked-list-cycle/
- */
-
 public class LinkedListCycle {
 
+    // 注意判空
     public boolean hasCycle(ListNode head) {
         for (ListNode fast = head, slow = head; fast != null && fast.next != null; ) {
             slow = slow.next;
diff --git a/leetcode/solution/src/MaximumSubarray.java b/leetcode/solution/src/MaximumSubarray.java
@@ -2,27 +2,23 @@ public class MaximumSubarray {
 
     // dp[i]表示包含第i个元素时的最大和
     public int maxSubArray(int[] nums) {
-        if (nums.length == 0) {
-            return 0;
-        }
         int[] dp = new int[nums.length];
         int max = Integer.MIN_VALUE;
         for (int i = 0; i < nums.length; i++) {
-            dp[i] = nums[i];
-            if (i > 0 && dp[i - 1] > 0) {
-                dp[i] += dp[i - 1];
-            }
+            dp[i] = Math.max(i > 0 ? dp[i - 1] + nums[i] : nums[i], nums[i]);
             max = Math.max(max, dp[i]);
         }
         return max;
     }
 
-    public int maxSubArray2(int[] nums) {
+    /* 这里dp其实可以去掉，换成一个普通int变量即可
+    public int maxSubArray(int[] nums) {
         int max = Integer.MIN_VALUE, prev = 0;
         for (int i = 0; i < nums.length; i++) {
-            prev = Math.max(nums[i], nums[i] + prev);
+            prev = Math.max(i > 0 ? prev + nums[i] : nums[i], nums[i]);
             max = Math.max(max, prev);
         }
         return max;
     }
+    */
 }
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -2,15 +2,21 @@
 
 public class Main {
 
-    public int maxArea(int[] height) {
-        int max = 0;
-        for (int i = 0, j = height.length - 1; i < j; ) {
-            max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
-            if (height[i] < height[j]) {
-                i++;
-            } else {
-                j--;
-            }
+    public int maxSubArray(int[] nums) {
+        int[] dp = new int[nums.length];
+        int max = Integer.MIN_VALUE;
+        for (int i = 0; i < nums.length; i++) {
+            dp[i] = Math.max(i > 0 ? dp[i - 1] + nums[i] : nums[i], nums[i]);
+            max = Math.max(max, dp[i]);
+        }
+        return max;
+    }
+
+    public int maxSubArray2(int[] nums) {
+        int max = Integer.MIN_VALUE, prev = 0;
+        for (int i = 0; i < nums.length; i++) {
+            prev = Math.max(i > 0 ? prev + nums[i] : nums[i], nums[i]);
+            max = Math.max(max, prev);
         }
         return max;
     }
