Blind 75
Maximum Subarray
- Problem
- LC 53
- Category
- Array
- File
- blind75_LC53MaximumSubarray.java
- Path
- pkg5leetcode/blind75/blind75_LC53MaximumSubarray.java
- Package
- pkg5leetcode.blind75
- Command
- java pkg5leetcode/blind75/blind75_LC53MaximumSubarray.java
- Approach
- Kadane's algorithm tracks best ending-here sum.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.blind75;2 3/*4 * Maximum Subarray | LC 535 * APPROACH: Kadane's algorithm tracks best ending-here sum.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC53MaximumSubarray {9 static int maxSubArray(int[] nums) {10 int best = nums[0], cur = nums[0];11 for (int i = 1; i < nums.length; i++) {12 cur = Math.max(nums[i], cur + nums[i]);13 best = Math.max(best, cur);14 }15 return best;16 }17 18 public static void main(String[] args) {19 check(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}) == 6, "case1");20 check(maxSubArray(new int[]{1}) == 1, "case2");21 System.out.println("all tests passed");22 }23 24 static void check(boolean cond, String name) {25 if (!cond) throw new AssertionError("FAILED: " + name);26 System.out.println(" PASS " + name);27 }28}