[剑指offer][Java]连续子数组的最大和

题目

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

程序核心思想

• 我的方法不太好，复杂度有点高，思路跟人工手算是一样的。
  首先分为三种情况：数组全为正，数组全为负，数组有正有负。

1. 数组全为正： 返回数组的和
2. 数组全为负： 返回数组中最大的一个数
3. 数组有正有负
   把每个元素当成子数组的开头进行求和，并且只求两个正数之间的和，如果有多个正数，则求其最大长度的正数的和。把所有的和存在一个数组中，返回其中最大的数。

• 参考别人的方法
  用一个tempmax代表前面的连续数字的最大和，如果这个最大和是正的，那么加上数组的当前数字，那么这个连续的和是变大的，这个就是有可能的潜在的最大和。

Tips

无

代码

import java.util.ArrayList;

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        ArrayList<Integer> answer = new ArrayList<Integer>();
        int start = 0;
        int pos = 0;
        int count = 0;
        boolean flag = true;
        int count2 = 0;
        int max1 = array[0];
        boolean flag2 = true;
        for(int i = 0; i < array.length; i++){
            if(array[i] >= 0){
                if(flag2){
                    start = i;
                    flag2 = false;
                }
                pos += array[i];
                count++;
            }else if(array[i] < 0){
                if(flag){
                     max1 = array[i];
                    count2++;
                    flag = false;
                }else{
                    if(array[i] > max1)    max1 = array[i];
                    count2++;
                }
            }
        }
        if(count == array.length){
            return pos;
        }else if(count2 == array.length){
            return max1;
        }
        for(int i = start; i < array.length; i++){
            for(int j = start + 1; j < array.length; j++){
                if(array[i] < 0)    break;
                if(array[j] > 0){
                    int sum = 0;
                    for(int p = i; p <= j; p++){
                        sum += array[p];
                    }
                    answer.add(sum);
                }
            }
        }
        
        int max = answer.get(0);
        for(int s : answer){
            if(s > max)    max = s;
        }
        return max;
    }
}

import java.util.ArrayList;

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int realMax = array[0];
        int currentMax = 0;
        
        for(int i = 0; i < array.length; i++){
            if(currentMax + array[i] >= array[i]){
                currentMax += array[i];
            }else{
                currentMax = array[i];
            }
            if(currentMax > realMax)    realMax = currentMax;
        }
        
        return realMax;
    }
}
···