/*
* 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个整数被空格和换行符隔开,表示按照行...
求一个二维数组中最大连通子数组的和
假设你有一个数组,而且这个数组中包含了数字的子数组,而我们要做的是从数组中的每个子数组中返回其最大的那个最大数。 基本解决方案 function largestOfFour(arr) { var results = []; // 创建一个results变量来...
:编写程序exp5_1.c,在主函数中定义一维数组int array[10],自定义以下函数:输入数组元素,输出数组元素、求数组元素平均值、输出数组元素最大值、输出数组元素最小值、查找某数值元素是否存在(若存在,...
给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字)。 2、代码详解 法一:可扩展性好(推荐) 二维数组,2*2大小,一维存最大值,一维存负最大值 class Solution(object)...
2. 建立两个int型的一维数组,分别起名为a和b,并完成以下任务: (1)编制一个判定某数是否为素数的子函数prime(参见3.17验证哥德巴赫猜想); (2)键盘输入15个数据(这些书中有奇数、也有偶数)存入数组a中; ...
今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,...
最大子矩阵是指在一个二维矩阵中,找到一个具有最大和的连续子矩阵。这个问题在计算机科学中...最大子数组问题是在一个一维数组中,找到一个具有最大和的连续子数组。在一维情况下,可以使用动态规划或分治算法来解决
今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。例如:{6,-3,-2,7,-15,
和每一维的大小: void foo(int *,int ,int);; int a[10][10];; foo(&a[0][0],10,10);; //... 十分的麻烦,在函数中访问时也得自己用乘法来计算元素的位置,更是十分麻烦. C99标准推出了可变大小的...
leetcode二维数组搜索leetcode 对于 Leetcode ...最大积子./152_maximum_product_subarray.c ./9_palindrome_number.c : 回文数,O(1)空间复杂度 ./14_longest_common_prefix.c : 最长公共前缀 ./19_Remo
%maxNsarvas ND 数组最大值,带下标输出% % X = MAXN(A) 返回作为第一个元素跟随的最大值% 由 A 的下标表示。事先不需要知道 A 的大小% 使用。 % % X = [最大值(A) sub1 sub2 sub3 . . . 子N]; % % 如果最大值出现...
leetcode二维数组力码 列表 #605. 可以放置鲜花 #581。 最短的未排序连续子阵列 #566。 重塑矩阵 #624。 数组中的最大距离 #532。 数组中的 K-diff 对 #414。 第三个最大数 细节 #605. 可以放花 问题描述: 假设你有...
leetcode二维数组 编程练习 包含常见的编程网站的练习习题(leetcode、牛客等)----待完成中... 也同时包含复习面试的编程练习 该src/main/java目录下,以文件夹命名,表示的是...连续子数组的最大和 整数中1出现的次数
leetcode二维数组为什么要分段树? 也称为区间树 也称为锦标赛树 用于运行范围总和查询 即给定范围内所有数字的总和 Prefix sum 用于获取范围和查询 如果输入数组不断发生变异,则前缀总和方法效果不佳 当输入频繁...
连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37.数字在排序数组中出现的次数40.数组中自出现过一次的数字50.数组中的重复数字51.构建乘积数组 数组篇 1.二维数组中的查找 在一个二维数组中(每个一维...
求和最大的子数组 在一个一维数组中,找到和最大的子数组(连续的任意个元素)
给定一个整数的二维数组,由其中若干邻近元素构成的矩形称为子数组。请编程计算所有子 数组元素之和的最大值。