第八章 最大自序列和

第八章的问题是常见的---最大自序列和 的问题

 

书中提供了几种求出最大和的方法，下面的实现是依据“扫描算法”的实现，不仅仅得到了最大和的值，还返回了对应自序列的索引起始值

 

package org.waitingfortime.编程珠玑.c8;

/**
 * Created by IntelliJ IDEA.
 * User: mazhiyuan
 * Date: 12-11-1
 * Time: 下午8:09
 * 最大子序列和，求得最大值，以及自序列索引值
 */
public class MaxSum {
    public static void main(String[] args) {
        int[] aa = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
        maxSum(aa);
    }

    public static int[] maxSum(int[] data) {
        int i = 0, start = 0, current = 0, end = 0, max = 0, sum = 0;

        while (i < data.length) {
            sum += data[i];
            if (sum > max) {
                end = i;
                start = current;
                max = sum;
            } else if (sum < 0) {
                sum = 0;
                current = i + 1;
            }

            i++;
        }

        int[] res = {max, start, end};
        
        return res;
    }
}

 

对“分治算法”的实现还有些疑惑，等彻底搞明白再说吧。