最新消息:请随时分享你的乐趣!

求最大子序列和问题—矮丑挫、高富帅算法

技术博客 磊子 566浏览 0评论

求最大子序列和问题

package test;

/**
 * 求最大子序列和
 * 问题: 
        给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大 
        例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
        对于这个问题,最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环,依次求出所有子序列的和然后取最大的那个。
        当然算法复杂度会达到O(n^3)。
 * @author lei
 *
 */
public class MaxSeqSum {

    //int[]arr={-6, 2, 4, -7, 5 ,3, 2 ,-1 ,6 ,-9, 10, -2};

    int[]arr={3, 4,-6, 7, -1 ,-2, 3 ,-1 ,6 ,-9, 10, -2};

    /**
     * 矮丑挫
     * 这种算法是普通人思维,也就是使用我需要把所有数据过一遍才能保证我的正确性。
     */
    private void commonSumMax() {
        int max=0;

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

            int thisSum=0;

            for(int j=i ;j<arr.length;j++){
                thisSum+=arr[j];

                if(max < thisSum){
                    max=thisSum;
                }
            }

        }
        System.out.println("max: " + max);
    }

    /**
     * 高富帅算法=时间+空间复杂度非常小,而且代码简单。结果可以实时在线获取。
     * 这个算法是聪明人分析数列结构后,根据数据性质得出来的概念
     * 分析根据:前面一段数相加如果是负的那么,最后这个数肯定非常负,而一般最优解不可能是以很烂数开始。
     * 而且结果可以实时联机获取。
     * @return
     */
    public void gfsSumMax() 
    { 
           long maxSum = 0, thisSum = 0; 
           for (int j = 0; j < arr.length; j++) 
           { 
                  thisSum += arr[j]; 
                  if (thisSum > maxSum) 
                         maxSum = thisSum; 
                  else if (thisSum < 0) 
                         thisSum = 0; 
           } 
           System.out.println("GfsMax"+maxSum);

    }



    public static void main(String[] args) {
        MaxSeqSum max= new MaxSeqSum();
        max.commonSumMax();
        max.gfsSumMax();
    }


}

参考:http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html

转载请注明:印迹. » 求最大子序列和问题—矮丑挫、高富帅算法

发表我的评论
取消评论

表情