数据结构学习

时间：2015-07-10 22:05:18 收藏：0 阅读：223

1.最大子序列和

给定N个整数的序列{A1、A2、A3......AN}，求最大子序列和，不要求求出对应序列。

方法1：

public class MaxSum {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int Temp = 0, MaxSum = 0;
        int num = in.nextInt();
        int[] a = new int[num];
        for (int i = 0; i < num; i++){
            a[i] = in.nextInt();
        }
        for (int i = 0; i < num; i++){
            Temp = 0;
            for (int j = i; j <= num; j++){
                Temp = Temp + a[j];
                if (Temp > MaxSum){
                    MaxSum = Temp;
                }
            }
        }
        System.out.println(MaxSum);
    }
}

该算法的时间复杂度为O(N²)

方法2：

分而治之

该算法的时间复杂度为O(NlogN)

方法3：

在线处理

该算法的时间复杂度为O(N)

原文：http://www.cnblogs.com/mxcsky/p/4637563.html