Minimum Subarray

Question

  1. Given an array of integers, find the subarray with smallest sum.
  2. Return the sum of the subarray.
  3. Example
  4. For [1, -1, -2, 1], return -3
  5. Note
  6. 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;
  8. int sum = 0, maxSum = 0, minSub = Integer.MAX_VALUE;
  9. for (int num : nums) {
  10. maxSum = Math.max(maxSum, sum);
  11. sum += num;
  12. minSub = Math.min(minSub, sum - maxSum);
  13. }
  14. return minSub;
  15. }
  16. }

源碼分析

複雜度分析