剑指offer-30-连续子数组的最大和

连续子数组的最大和

http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484

思路

求连续某一段和,即求累积和,sum[i]表示从0-i的累积和
累计和的最大与最小值之差即为连续最大和,但是要处理一种特殊情况,即数据全为负数

代码

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){return 0;}
        int[] sum=new int[array.length+1];
        int max=0,min=Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++){
            sum[i+1]+=sum[i]+array[i];
            min=Math.max(min,array[i]);
        }
        if(min<0){return min;}
        for(int i=0;i<sum.length;i++){
            min=Math.min(min,sum[i]);
            max=Math.max(max,sum[i]-min);

        }
        return max;
    }
}
剑指offer与数据结构 文章被收录于专栏

本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务