`
jiq408694711
  • 浏览: 32551 次
  • 性别: Icon_minigender_1
  • 来自: 南京
文章分类
社区版块
存档分类
最新评论

一维子数组最大和

 
阅读更多
/*
 * MaxSumSubArray.cpp
 *
 *  Created on: 2012-6-20
 *      Author: jiyiqin
 *
 *  给定一个包含正数,负数,0的数组,求一个连续的子数组,使得其和最大
 */
#include <iostream>
using namespace std;

#define MIN_INT -10000
class MaxSumOfSubArray{
public:

	/**
	 * 二重循环查找最大和子数组,依次以a[i]为起点,
	 * 求解sum[i,j],更新当前最大和的值
	 * 注意数组全是负数的情况
	 * */
	static int m1_subArray(int a[], int size)
	{
		int max_sum = MIN_INT;					//max赋值一次
		if(a == NULL || size <=0) return -1;	//输入是否合法判断

		for(int i=0;i<size;i++)
		{
			int sum = 0;
			for(int j=i;j<size;j++){
				sum += a[j];
				if(sum > max_sum) max_sum = sum;	//更新max
			}
		}
		cout<<"max_sum:"<<max_sum<<endl;
		return 1;
	}

	/**
	 * 线性时间完成:
	 * 记录当前max,逐个累加
	 * 如果和sum变成负,丢弃(更新起点)。
	 * 如果sum > max,更新max。
	 * 注意数组全部是负数的时候,"负数和"也拥有和当前最大和比较的权利
	 * */
	static int m2_subArray(int a[], int size)
	{
		int max_sum = MIN_INT;					//最大和初值为最小数字
		int sum = 0;
		if(a == NULL || size <=0) return -1;	//输入是否合法判断

		for(int i=0;i<size;i++)
		{
			sum += a[i];
			if(sum > max_sum) max_sum = sum;	//更新max
			if(sum <= 0) sum = 0;				//重新开始计算和
		}
		cout<<"max_sum:"<<max_sum<<endl;
		return 1;
	}

	/**
	 * 动态规划方法:
	 * 很明显求解最大子数组和的问题有子结构,并且满足“无后效性”。
	 * 即问题可以被划分为多个阶段,未来阶段状态f(i+1)的求解仅仅与
	 * 当前状态f(i)通过状态转移方程得到,而与过去的历史状态无关。
	 * 我们设sum(i)为以a[i]结尾的最大子数组和.
	 *
	 * 如果sum(i-1) =< 0:
	 * 		很明显我们不应当将其简单抛弃,因为我们还要考虑数组a全部都是负数的情况,
	 * 		所以我们仍然将其与a[i]比较,所以sum(i) = max{sum(i-1), a[i]};
	 * 如果sum(i-1) > 0:
	 * 		因为sum(i-1)是以a[i-1]结尾的,所以很明显sum(i) = sum(i-1)+a[i];
	 * 所以我们得到状态转移方程如下:
	 * sum(i) =
	 * 		sum(i-1)+a[i];			sum(i-1) > 0
	 * 		max{sum(i-1), a[i]};	sum(i-1) <= 0
	 * */
	static int m3_subArray(int a[], int size)
	{
		int *sum = new int[size];
		int max_sum = MIN_INT;
	
		if(a == NULL || size <= 0) return -1;	//判断输入是否合法
		for(int k=0;k<size;k++) sum[k] = 0;		//初始化sum数组

		//顺着i自底向上求解
		sum[0] = a[0];
		for(int i=1;i<size;i++)
		{
			if(sum[i-1] > 0) sum[i] = sum[i-1]+a[i];
			else sum[i] = sum[i-1]>a[i]?sum[i-1]:a[i];
			
			//更新max_sum
			if(sum[i] > max_sum) max_sum = sum[i];
		}
		
		//输出结果
		cout<<"max_sum:"<<max_sum<<endl;
		for(int j=0;j<size;j++)
			cout<<sum[j]<<" ";
		cout<<endl;
		return 1;
	}

	static void test(){
		int a[10] = {-1,2,-5,2,-1,-13,15,-2,8,-1};
		for(int i=0;i<10;i++){
			cout<<a[i]<<" ";
		}
		cout<<endl;

		m1_subArray(a, 10);	//方法1
		m2_subArray(a, 10);	//方法2
		m3_subArray(a, 10);	//方法3
	}
};

int main(){
	MaxSumOfSubArray::test();
	return 0;
}

分享到:
评论

相关推荐

    求二维数组最大和的子数组

    给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行是一个整数N,表示二维数组的大小为N*N。接下来的N*N个数被空格和换行符隔开,表示按照...

    求二维数组的最大和的子数组

    给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行为整数N,代表二维数组的大小为N*N。接下来的N*N个整数被空格和换行符隔开,表示按照行...

    求二维数组中的最大连通子数组的和

    求一个二维数组中最大连通子数组的和

    JS中取二维数组中最大值的方法汇总

    假设你有一个数组,而且这个数组中包含了数字的子数组,而我们要做的是从数组中的每个子数组中返回其最大的那个最大数。 基本解决方案 function largestOfFour(arr) { var results = []; // 创建一个results变量来...

    实验四 一维与二维数组实验

    :编写程序exp5_1.c,在主函数中定义一维数组int array[10],自定义以下函数:输入数组元素,输出数组元素、求数组元素平均值、输出数组元素最大值、输出数组元素最小值、查找某数值元素是否存在(若存在,...

    DP-LeetCode152. 乘积最大子数组(Python)

    给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...

    西南交通大学计算机程序设计基础-实验8-C++.docx

    2. 建立两个int型的一维数组,分别起名为a和b,并完成以下任务: (1)编制一个判定某数是否为素数的子函数prime(参见3.17验证哥德巴赫猜想); (2)键盘输入15个数据(这些书中有奇数、也有偶数)存入数组a中; ...

    Python语言描述连续子数组的最大和

    今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,...

    最大子矩阵概述.pdf

    最大子矩阵是指在一个二维矩阵中,找到一个具有最大和的连续子矩阵。这个问题在计算机科学中...最大子数组问题是在一个一维数组中,找到一个具有最大和的连续子数组。在一维情况下,可以使用动态规划或分治算法来解决

    G-MIng#JAVA2019#面试题42. 连续子数组的最大和1

    今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。例如:{6,-3,-2,7,-15,

    一组新的多维数组模板类

    和每一维的大小: void foo(int *,int ,int);; int a[10][10];; foo(&a[0][0],10,10);; //... 十分的麻烦,在函数中访问时也得自己用乘法来计算元素的位置,更是十分麻烦. C99标准推出了可变大小的...

    leetcode二维数组搜索-leetcode:C中一些算法问题的解决

    leetcode二维数组搜索leetcode 对于 Leetcode ...最大积子./152_maximum_product_subarray.c ./9_palindrome_number.c : 回文数,O(1)空间复杂度 ./14_longest_common_prefix.c : 最长公共前缀 ./19_Remo

    N维数组的最大值或最小值:这些函数返回数组中最大值或最小值的下标-matlab开发

    %maxNsarvas ND 数组最大值,带下标输出% % X = MAXN(A) 返回作为第一个元素跟随的最大值% 由 A 的下标表示。事先不需要知道 A 的大小% 使用。 % % X = [最大值(A) sub1 sub2 sub3 . . . 子N]; % % 如果最大值出现...

    leetcode二维数组-LeetCode:力码

    leetcode二维数组力码 列表 #605. 可以放置鲜花 #581。 最短的未排序连续子阵列 #566。 重塑矩阵 #624。 数组中的最大距离 #532。 数组中的 K-diff 对 #414。 第三个最大数 细节 #605. 可以放花 问题描述: 假设你有...

    leetcode二维数组-programming_exercises:leetcode、nowcoder刷题之路

    leetcode二维数组 编程练习 包含常见的编程网站的练习习题(leetcode、牛客等)----待完成中... 也同时包含复习面试的编程练习 该src/main/java目录下,以文件夹命名,表示的是...连续子数组的最大和 整数中1出现的次数

    leetcode二维数组-segment-tree:段树

    leetcode二维数组为什么要分段树? 也称为区间树 也称为锦标赛树 用于运行范围总和查询 即给定范围内所有数字的总和 Prefix sum 用于获取范围和查询 如果输入数组不断发生变异,则前缀总和方法效果不佳 当输入频繁...

    (一)剑指offer—Python版—数组篇

    连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37.数字在排序数组中出现的次数40.数组中自出现过一次的数字50.数组中的重复数字51.构建乘积数组 数组篇 1.二维数组中的查找 在一个二维数组中(每个一维...

    max_sum.rar_SUM_max_sum

    求和最大的子数组 在一个一维数组中,找到和最大的子数组(连续的任意个元素)

    最大数组合

    给定一个整数的二维数组,由其中若干邻近元素构成的矩形称为子数组。请编程计算所有子 数组元素之和的最大值。

Global site tag (gtag.js) - Google Analytics