现在的位置: 首页 > 编程技术 > Java > 编程技术 > 算法学习 > 正文

最大子序列和问题

2014年12月26日 Java, 算法学习 ⁄ 共 961字 ⁄ 字号 最大子序列和问题已关闭评论 ⁄ 阅读 587 次

这几天学习算法,遇到的第一个问题是最大子序列和.问题的描述为:

给定(可能有负数)整数序列A1, A2, A3..., An, 求这个序列中子序列和的最大值。(为方便起见,如果所有整数均为负数,则最大子序列和为0)。

public class maxsum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = { -9, -2, -3, -5, -3 };
		//int a[] = { -9, 1,4,9,-8,7,6,9,-1 };
		//int a[] = {-6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2 };
		int thissum = 0;
		int maxsum = 0;
		int n = a.length;
		for (int i = 0; i < n; i++) {
			thissum = thissum + a[i];
			if (thissum > maxsum) {
				maxsum = thissum;
			} else if (thissum < 0) {
				thissum = 0;
			}
		}
		System.out.println(maxsum);
	}
}

还有一种可能遇到的变形形式的问题:给定(可能有负数)整数序列A1, A2, A3..., An, 求这个序列中子序列和的最大值。(最大值可以为负数)

public class maxsum_neg {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// int a[] = { -9, -2, -3, -5, -3 };
		//int a[] = { -9, 1,4,9,-8,7,6,9,-1 };
		int a[] = {-6, 2, 4, -7, 5, 3, 2, -1, 6, -9, 10, -2 };
		int thissum = 0;
		int maxsum = a[0];
		int n = a.length;
		for (int i = 0; i < n; i++) {
			thissum = thissum + a[i];
			if (thissum > maxsum) {
				maxsum = thissum;
			} else if (thissum < 0) {
				thissum = 0;
			}
		}
		System.out.println(maxsum);
	}
}

这里的区别在于起始的最大值的设定,第一种情况为0,那么最大值最小也是0,第二种最大值的初始值是a[0](也可以随便一个a[x],这样就保证了结果最大值可以为负(如果最大值都为负,那么每个值肯定都为负)。

【上篇】
【下篇】

抱歉!评论已关闭.