最大子数组

题意

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

样例

给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为 6

思路

对数组进行遍历,每次取当前角标的数,加上 sum 值,如果 sum 值大于现存的最大值,那么则将 sum 赋值给 max,如果 sum 小于 0,则将 sum 重置为 0,直到循环结束。

代码实现

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = sum > max ? sum : max;
            sum = sum > 0 ? sum : 0;
        }
        
        return max;
    }
}

原题地址

LintCode:最大子数组

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(二十五) ——并归排序

PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

3908
来自专栏张俊红

python中的小魔法(一)

? 总第101篇 if-else的简洁写法 #常规写法 if a>b: c=a else: c=b #简洁写法 c=a if a>b...

2744
来自专栏机器学习算法与Python学习

python基础语法(1)

从今天起,将进行python的一个系列学习,从基本的语法学起,后期会推出一些关于web开发,网络爬虫以及用python的第三方库进行数据挖掘与机器学习等高级的开...

39114
来自专栏Android机器圈

数据结构与算法 -- 栈的应用(进制转换、括号匹配)

ps:用栈很简单实现的应用有很多,比如说进制转换,括号匹配等。学计算机的都知道,2进制,8进制,10进制,16进制等,进制之间的转换也是需要掌握的,以备不时之需...

2012
来自专栏代码世界

Python之迭代器和生成器

迭代器 可迭代的数据类型: list   dic   str    set     tuple      f=open()--文件句柄      range  ...

39011
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理

《Redis设计与实现》读书笔记(九) ——Redis集合和有序集合实现原理 (原创内容,转载请注明来源,谢谢) 一、集合 集合的编码方式有intset和has...

3055
来自专栏数说戏聊

SUBSTRING() 与 CONV() 函数1.substring()函数2.conv()函数

MySQL 字符串截取函数:left(), right(), substring(), substring_index()。

862
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3447
来自专栏Java面试笔试题

两个栈实现一个队列

由于往栈中添加元素相当于往队列头添加元素,因此我们需要在两个队列中进行元素的转移,比较简单的实现是:

983
来自专栏软件开发 -- 分享 互助 成长

sizeof(结构体)的计算

摘要: 经常被计算结构体的sizeof给搞晕,于是找了个时间,静下心来,搞定它。 一、为什么结构体计算这么乱? 答案是字节对齐,计算机存储系统中以Byte为单位...

3139

扫码关注云+社区

领取腾讯云代金券