LintCode 最小子数组 && 最大子数组题目分析代码最大子数组

题目

给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。

** 注意事项 子数组最少包含一个数字 **

样例 给出数组[1, -1, -2, 1],返回 -3

分析

判断加与不加的情况,这道题的解法很巧妙,类似于背包问题。 每个数组的元素都有两种情况,加与不加,所以我们从第一个元素开始判断,包括第一个元素时,和不包括第一个元素的情况取最小值,进行判断选择。

代码

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        // write your code
        int min_ending_here = nums.get(0);
        int min_so_far = nums.get(0);
        for(int i=1;i<nums.size();i++)
        {
            min_ending_here = Math.min(nums.get(i), nums.get(i)+ min_ending_here);
            min_so_far = Math.min(min_ending_here, min_so_far);
        }
        return min_so_far;
    }
}

最大子数组

这道题的思路和最小子数组是一样的,只要更改判断小为判断大就可以了 这里就直接贴出代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        int max_ending_here = nums[0];
        int max_so_far = nums[0];
        for( int i =1 ;i<nums.length; i++) {
            max_ending_here = Math.max( nums[i] , nums[i] + max_ending_here );
            max_so_far = Math.max( max_so_far, max_ending_here);
        }
        return max_so_far;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

761
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

1003
来自专栏desperate633

LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

912
来自专栏mathor

波兰表达式

1424
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

42710
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

3566
来自专栏从零开始学 Web 前端

05 - JavaSE之数组

1454
来自专栏尾尾部落

[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

982
来自专栏运维技术迷

PHP-数组排序

分别定义一个数值数组和一个关联数组. $age=array("lili"=&gt;"23","bob"=&gt;"30","ben"=&gt;"44"); $c...

3106
来自专栏眯眯眼猫头鹰的小树杈

leetcode 343. Integer Break

这里应用了一个数学的思路。假设我们有一个数字n,该数组可以随机分解为t和n-t。当分解为n/2时可以获得最大的乘积。因此t取n/2时可以得到最好的结果。但是这里...

893

扫码关注云+社区

领取腾讯云代金券