最大子序列问题

最大子序列问题

给定一个数列，其中的数有正有负，求这个数列中的某一个子序列使得它们的和最大。

例如：

-2, 11, -4, 13, -5, 2, -5, -3, 12, -9 这个数列中，子序列和最大为21

-2 ,11, -4, 13, -5, -2 和为20 思路：

traverse整个数组

用sum存储当前位置及其之前的数字之和

因为每次循环都会求得一个sum，用max存储最大的sum

如果某一次求得的sum<0，则另sum=0，意思是抛弃之前所有的元素，从之后的元素重新开始求和。

public class Maxsubarray {

    public int maxsum(int[] array){

        if(array.length == 0) return 0;

        else if(array.length == 1) return array[0];

        else{

            int sum = 0;

            int max = sum;

            for(int i = 0; i < array.length; i++){

                if(max < sum) max = sum;

                sum = sum + array[i];

                if(sum < 0)

                    sum = 0;

            }

            return max;

        }

    }

    public static void main(String[] args) {

        int array[] = {-2 ,11, -4, 13, -5, -2};

        Maxsubarray ms = new Maxsubarray();

        System.out.println(ms.maxsum(array));

    }

}

时间复杂度由n规模的for循环贡献，因此是O(n)