首页 > 代码库 > Lintcode: Minimum Subarray 解题报告
Lintcode: Minimum Subarray 解题报告
Minimum Subarray
原题链接： http://lintcode.com/zh-cn/problem/minimum-subarray/#
Given an array of integers, find the subarray with smallest sum.
Return the sum of the subarray.
注意
The subarray should contain at least one integer.
样例
For [1, -1, -2, 1], return -3
标签 Expand
SOLUTION 1：
1. 我们把整个array * -1，把它转化为求最大和的题目。
2. 然后我们可以使用Sliding window的方法来做。记录一个sum，如果发现sum<0 则丢弃，否则不断把当前的值累加到sum，
3. 每计算一次sum,求一次max.
4. 返回-max即可。
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 // write your code 8 9 int len = nums.size();10 11 int max = Integer.MIN_VALUE;12 int sum = 0;13 for (int i = 0; i < len; i++) {14 if (sum < 0) {15 sum = -nums.get(i);16 } else {17 sum += -nums.get(i);18 }19 20 max = Math.max(max, sum);21 }22 23 return -max;24 }25 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/array/SubarraySum.java
Lintcode: Minimum Subarray 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。