第八章 最大自序列和

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

?

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

?

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;    }}

?

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