第八章 最大发刊词列和
第八章 最大自序列和
第八章的问题是常见的---最大自序列和 的问题
书中提供了几种求出最大和的方法,下面的实现是依据“扫描算法”的实现,不仅仅得到了最大和的值,还返回了对应自序列的索引起始值
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; } }
对“分治算法”的实现还有些疑惑,等彻底搞明白再说吧。