剑指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题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构