Refactor for Kadane

NinaWan · NinaWan · commit 8d16169f47db · 2024-12-16T11:48:29.000+08:00
diff --git a/src/main/java/array/subarray/kadane/Kadane.java b/src/main/java/array/subarray/kadane/Kadane.java
@@ -0,0 +1,14 @@
+package array.subarray.kadane;
+
+public class Kadane {
+    public int maxSubArray(int[] nums) {
+        int ans = nums[0], dp = nums[0];
+
+        for (int i = 1; i < nums.length; i++) {
+            dp = Math.max(dp + nums[i], nums[i]);
+            ans = Math.max(ans, dp);
+        }
+
+        return ans;
+    }
+}
diff --git a/src/main/java/array/subarray/kadane/kadane.md b/src/main/java/array/subarray/kadane/kadane.md
@@ -33,6 +33,10 @@ class Kadane {
 }
 ```
 
-## &#26102;&#38388;&#22797;&#26434;&#24230;
+## &#22797;&#26434;&#24230;
 
-O(n)
+### &#26102;&#38388;&#22797;&#26434;&#24230;
+
+O(n)
+
+### &#31354;&#38388;&#22797;&#26434;&#24230;
diff --git a/src/test/java/array/subarray/kadane/KadaneTest.java b/src/test/java/array/subarray/kadane/KadaneTest.java
@@ -0,0 +1,22 @@
+package array.subarray.kadane;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class KadaneTest {
+    private Kadane tested;
+    private int[] nums;
+
+    @BeforeEach
+    void setup() {
+        nums = new int[]{64, -25, 42, 10, -70, 22, 35, -96, 61, 49};
+        tested = new Kadane();
+    }
+
+    @Test
+    void maxSubArray() {
+        assertEquals(110, tested.maxSubArray(nums));
+    }
+}

-Original file line number
+Diff line change
+}
 ```
 -## 时间复杂度
 +## 复杂度
 -O(n)
 +### 时间复杂度
++
 +O(n)
++
 +### 空间复杂度