Minimum Subarray

Question

  1. Given an array of integers, find the subarray with smallest sum.
  3. Return the sum of the subarray.
  5. Example
  6. For [1, -1, -2, 1], return -3
  8. Note
  9. The subarray should contain at least one integer.

題解

題目 Maximum Subarray 的變形，使用區間和容易理解和實現。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: a list of integers
  4.      * @return: A integer indicate the sum of minimum subarray
  5.      */
  6.     public int minSubArray(ArrayList<Integer> nums) {
  7.         if (nums == null || nums.isEmpty()) return -1;
  9.         int sum = 0, maxSum = 0, minSub = Integer.MAX_VALUE;
  10.         for (int num : nums) {
  11.             maxSum = Math.max(maxSum, sum);
  12.             sum += num;
  13.             minSub = Math.min(minSub, sum - maxSum);
  14.         }
  16.         return minSub;
  17.     }
  18. }

源碼分析

略

複雜度分析

略