下载文档原格式
最大字段和问题1.实验题目给定由N 个整数（可能有负整数）组成的序列（1a ，2a ，…，n a ），求该序列形如∑=j i k k a的子段和的最大值，当所有整数均为负整数是，其最大子段和为0。
2.实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。
3.实验分析蛮力法：利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。
用了3个for 嵌套所以时间复杂性为○(n 3)。
分治法：（1）划分：按照平衡子问题的原则，将序列（1a ，2a ，…，n a ）划分成长度相同的两个字序列（1a ，…，⎣⎦2/n a ）和（⎣⎦12/+n a ，…，n a ）。
（2）求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1=⎣⎦⎣⎦)2/1(max 2/n i a n i k k ≤≤∑=，s2=⎣⎦⎣⎦)2/(max 12/n j n a j n k k≤≤∑+=，则s1+s2为最大子段和。
若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。
（3）合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。
（4）时间复杂性分析: f(n) = 2*f(n/2) + ○(n/2), 最后为○(nlogn)。
动态规划法：动态规划法求解最大字段和问题的关键是要确定动态规划函数。
记)1(max )(1n j a j b i i k k j i ≤≤⎭⎬⎫⎩⎨⎧=∑=≤≤ 则{})(max max max max 1111j b a a n j j i k k j i n j ji k k n j i ≤≤=≤≤≤≤=≤≤≤=⎭⎬⎫⎩⎨⎧=∑∑ 由b （j ）的定义，当b （j-1）>0是，b （j ）=b （j-1）+a ，否则，b （j ）=a 。
怎么求数组的最大子序列和如何求解数组的最大子序列和在计算机科学和算法设计中，求解数组的最大子序列和是一个常见的问题。
给定一个整数数组，我们的目标是找到一个连续子数组，使得子数组的和最大。
本文将介绍两种常见的解决方法，并分析它们的时间复杂度和空间复杂度。
方法一：暴力法最简单直观的方法是使用两层循环遍历所有可能的子数组，计算它们的和，并记录下最大的和。
具体步骤如下：1. 初始化一个变量maxSum为数组中第一个元素的值，用于记录最大子序列和。
2. 通过两层循环遍历所有可能的子数组：a. 外层循环从0到n-1遍历数组的起始位置。
b. 内层循环从外层循环的当前位置到n-1遍历数组的结束位置。
c. 在内层循环中，计算当前子数组的和，并将其与maxSum比较，如果大于maxSum，则更新maxSum的值。
3. 返回maxSum作为最大子序列和。
这种方法的时间复杂度为O(n^2)，因为我们需要遍历所有可能的子数组。
空间复杂度为O(1)，因为我们只需要常数级别的额外空间。
方法二：动态规划动态规划是一种通过将原问题分解为子问题来求解的方法。
对于数组的最大子序列和，我们可以定义一个状态数组dp，其中dp[i]表示以第i个元素结尾的子数组的最大和。
具体步骤如下：1. 初始化一个状态数组dp，长度为n。
2. 初始化dp[0]为数组的第一个元素的值。
3. 从1到n-1遍历数组，对于每个元素arr[i]，更新dp[i]的值为max(arr[i], dp[i-1]+arr[i])。
4. 最终的最大子序列和为dp数组中的最大值。
这种方法的时间复杂度为O(n)，因为我们只需要遍历一次数组。
空间复杂度为O(n)，因为我们需要一个长度为n的状态数组。
对比两种方法，动态规划方法具有更低的时间复杂度和更好的空间复杂度。
因此，在实际应用中，我们通常使用动态规划来求解数组的最大子序列和问题。
除了上述两种方法，还有其他一些优化的方法，如分治法和贪心法。
子数组的最大和1. 任务背景子数组是指在原始数组中连续的一段元素组成的子序列。
子数组的最大和是指在所有可能的子数组中，元素之和最大的子数组。
在算法和数据结构中，求解子数组的最大和是一个常见的问题。
它有着广泛的应用场景，例如金融领域的股票交易分析、图像处理中的边缘检测等。
2. 问题描述给定一个整数数组，求解其子数组的最大和。
例如，对于数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，其子数组的最大和为6，对应的子数组为[4, -1, 2, 1]。
3. 解决思路3.1 暴力法最简单直观的方法是使用暴力法，遍历所有可能的子数组，并计算其和，找到最大的和。
算法步骤如下：1.初始化最大和max_sum为数组中第一个元素。
2.遍历数组中的每个元素num，从第二个元素开始。
3.对于每个元素，计算以它为结尾的子数组的和cur_sum，并更新max_sum为max(max_sum, cur_sum)。
4.返回最大和max_sum。
该算法的时间复杂度为O(n^2)，其中n为数组的长度。
3.2 动态规划通过观察可以发现，以第i个元素为结尾的子数组的最大和，要么是第i-1个元素为结尾的子数组的最大和加上第i个元素，要么是只包含第i个元素。
定义一个动态规划数组dp，其中dp[i]表示以第i个元素为结尾的子数组的最大和。
动态规划的状态转移方程如下：dp[i] = max(dp[i-1] + nums[i], nums[i])算法步骤如下：1.初始化动态规划数组dp，将其元素全部初始化为0。
2.初始化最大和max_sum为数组中第一个元素。
3.遍历数组中的每个元素num，从第二个元素开始。
4.对于每个元素，更新动态规划数组dp[i]为max(dp[i-1] + num, num)。
5.更新最大和max_sum为max(max_sum, dp[i])。
6.返回最大和max_sum。
该算法的时间复杂度为O(n)，其中n为数组的长度。
最⼤字段和问题最⼤⼦段和 -- 分治,dp1.问题描述输⼊⼀个整型数组，数组中的⼀个或连续多个整数组成⼀个⼦数组。
求所有⼦数组的和的最⼤值。
⽰例1:输⼊: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续⼦数组 [4,-1,2,1] 的和最⼤，为 6。
2.分析问题2.1 ⽅案1此题很显然可以⽤多层for循环解决, 时间复杂度为O(n^2) .2.2 ⽅案2, 图像压缩问题的变形采⽤dp的思路, 我们把这个数组分成不同的段, **dp[i] 表⽰以nums[i]结尾的那个段的最⼤字段和, 所以就存在nums[i]这个元素是加⼊前⼀段中, 还是⾃成⼀段这就是需要思考的问题, 如果dp[i-1] < 0, 如果nums[i]加⼊前⼀段中, 最⼤字段和为dp[i-1] + nums[i], 这个值必然⼩于nums[i], 因为dp[i-1]是负数, 负数加上⼀个数,必然⽐这个数⼩, 就像是⼀个数减了某个数, 肯定变⼩. 其他情况下只⽤求dp[i-1] + nums[i]和 nums[i] 的最⼤值即可 **通过上⾯的分析, 很容易写出状态转移⽅程// dp初始化dp[0] = nums[0]if(dp[i-1] < 0) dp[i] = nums[i]; // ⾃成⼀段if(dp[i-1] >= 0) dp[i] = Max(dp[i-1] + nums[i], nums[i])简化转移⽅程, dp[i-1]<0时, nums[i] + dp[i-1] 必然是⼩于nums[i]的, 其实也是在求Max(dp[i-1] + nums[i], nums[i]),所以这个题只⽤⼀个⽅程就搞定. 简化了if else的判断, 对程序性能提升也是有帮助的dp[0] = nums[0]dp[i] = Max(dp[i-1] + nums[i], nums[i])这个题很有个很坑的地⽅就是, dp中最后⼀个元素并不是最终要求的结果, 这个我们平时做的题有很⼤的出⼊, dp[i]的含义是以nums[i]结尾的那个段的最⼤字段和, 那么dp中最后⼀个元素表⽰的是以nums中最后⼀个元素结尾的那个段的最⼤字段和, 最⼤的字段和不⼀定以nums中最后⼀个元素结尾,所以要最终要求的⽬标是dp数组中的最⼤值public int maxSubArray(int[] nums) {if(nums == null || nums.length <= 0) throw new IllegalArgumentException();int[] dp = new int[nums.length];dp[0] = nums[0];for(int i = 1; i < nums.length; ++i){dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);}// return dp[nums.length-1]; 神坑int maxValue = Integer.MIN_VALUE;for(int j = 0; j < dp.length; ++j){if(dp[j] > maxValue)maxValue = dp[j];}return maxValue;3. ⽅案3采⽤分治的思路, 我们把数组从中间分开, 最⼤⼦序列的位置就存在以下三种情况最⼤⼦序列在左半边, 采⽤递归解决最⼤⼦序列在右半边, 采⽤递归解决最⼤⼦序列横跨左右半边, 左边的最⼤值加上右边的最⼤值时间复杂度分析T(n) = 2 F(n/2) + n时间复杂度O(nlgn)public int maxSubArray(int[] nums) {if(nums == null || nums.length <= 0) throw new IllegalArgumentException(); return helper(nums, 0, nums.length-1);}private int helper(int [] nums, int start, int end){if(nums == null || nums.length <= 0) throw new IllegalArgumentException(); if(start == end)return nums[start];int middle = start + (end - start) / 2;int leftSums = helper(nums,start, middle);int rightSums = helper(nums,middle+1, end);// 横跨左右两边int leftRightSums;// 左边的最⼤值int lsums = Integer.MIN_VALUE, temp = 0;for(int i = middle; i >= start; i--){temp += nums[i];if(temp > lsums)lsums = temp;}// 右边的最⼤值int rsums = Integer.MIN_VALUE;temp = 0;for(int j = middle+1; j <= end; j++){temp += nums[j];if(temp > rsums) rsums = temp;}leftRightSums = rsums + lsums;return Math.max(Math.max(leftSums, rightSums), leftRightSums);}。
昆明理工大学信息工程与自动化学院学生实验报告（ 2011 — 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房444 2012 年12月 14日一、上机目的及内容1.上机内容给定有n 个整数（可能有负整数）组成的序列（a 1,a 2,…,a n ），求改序列形如∑=jk ka1的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。
2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； 蛮力法设计原理：利用3个for 的嵌套（实现从第1个数开始计算子段长度为1，2，3…n 的子段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n 个数开始计算的长为1的子段和）和一个if （用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。
用了3个for 嵌套所以时间复杂性为○(n 3)；分治法设计原理：1）、划分：按照平衡子问题的原则，将序列（1a ，2a ，…，na ）划分成长度相同的两个字序列（1a ，…，⎣⎦2/n a ）和（⎣⎦12/+n a ，…，na ）。
2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1=⎣⎦⎣⎦)2/1(max2/n i an ik k≤≤∑=，s2=⎣⎦⎣⎦)2/(max12/n j n ajn k k≤≤∑+=，则s1+s2为最大子段和。
若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。
3）、合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。
标题：如何在10个字段中查询最大的值的字段在数据分析和处理中，我们经常会面对一个问题：在多个字段中找到最大值所在的字段。
这在实际工作中非常常见，因此掌握如何高效地进行这一操作是非常重要的。
本文将介绍如何在10个字段中查询最大的值的字段，希望对大家有所帮助。
1. 理解需求在进行任何操作之前，首先要对需求进行充分的理解和分析。
在这个问题中，我们需要在给定的10个字段中找到最大值所在的字段。
这意味着我们需要逐一比较这10个字段的值，并找到其中的最大值所在的字段位置。
2. 使用函数进行比较在大多数数据处理软件中，都提供了函数来进行字段之间的比较。
在Excel中，可以使用IF函数来逐一比较这10个字段的值，然后找到最大值所在的字段。
在SQL数据库中，也可以使用CASE WHEN语句来进行类似的操作。
3. 编写代码如果数据量较大，手工逐一比较这10个字段的值显然是不现实的。
我们可以编写代码来自动化这一过程。
在Python、R、Java等编程语言中，都可以编写简洁高效的代码来实现这一需求。
使用循环结构和条件判断，可以让计算机帮助我们完成这一繁琐的工作。
4. 使用内置函数在某些数据处理软件和编程语言中，也提供了内置的函数来方便我们进行字段间比较。
在SQL中，可以使用MAX函数来找到最大值，并结合其他函数来得到最大值所在的字段。
在R语言中，也有max.col函数来实现类似的功能。
5. 注意异常值处理在进行字段间比较时，我们还需要考虑到可能存在的异常值。
如果字段中存在缺失值或者特殊字符，会对比较结果造成影响。
我们需要在进行比较之前进行数据清洗和异常值处理，以确保比较结果的准确性。
6. 考虑效率问题在实际操作中，可能会遇到大规模数据的情况，因此比较的效率也是一个需要考虑的问题。
我们应该尽量选择高效的算法和函数来进行比较，以减少计算时间。
7. 测试和验证在编写代码或者使用内置函数进行比较之后，我们需要进行测试和验证，以确保得到的结果是准确的。
动态规划法求最大子段和
#include
void MaxSum(int n,int a[])
{
int sum=0;
int b=0;
for(int i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
cout<<"整数序列的最大子段和是："<
void main()
{
int n,a[100],m,maxsum;
cout<<"请输入整数序列的元素个数n:"<
cout<<"请输入各元素的值(一共"<
cin>>a[m];
MaxSum(n,a);
}
选择题在计算最大字段和时，若数组为全负数，则最大字段和为：A. 数组中的最大值B. 数组中的最小值（正确答案）C. 数组所有元素之和D. 0给定数组[1, -2, 3, -4, 5]，其最大字段和是：A. 1B. 3C. 5（正确答案）D. 1+(-2)+3+(-4)+5对于一个包含n个元素的数组，计算最大字段和的时间复杂度最坏情况下可以是：A. O(1)B. O(n)（正确答案）C. O(n2)D. O(nlogn)若数组中存在多个连续子数组，它们的和相等且为最大值，则最大字段和算法返回的是：A. 第一个出现的子数组的和B. 任意一个这样的子数组的和（正确答案）C. 最后一个出现的子数组的和D. 所有这些子数组和的平均值给定数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，以下哪个子数组的和是该数组的最大字段和？A. [4, -1, 2, 1]B. [1, -3, 4, -1, 2, 1]（正确答案）C. [-2, 1, -3, 4]D.在计算最大字段和时，若数组为空，则通常约定最大字段和为：A. -∞B. 0（正确答案）C. ∞D. 未定义使用Kadane算法计算最大字段和时，需要维护的主要变量是：A. 当前子数组的最大和与全局最大和（正确答案）B. 当前元素的值与全局最大和C. 当前子数组的长度与全局最大和D. 当前子数组的起始位置与全局最大和给定数组[2, 3, -2, 4]，若只允许选择连续的两个元素作为子数组，则最大字段和为：A. 2+3B. 3+(-2)C. -2+4D. 3+4（正确答案）在求解最大字段和的问题中，以下哪个策略不是有效的？A. 遍历所有可能的子数组，计算它们的和，并找出最大值B. 使用动态规划方法，通过维护局部最优解来找到全局最优解C. 利用分治法，将问题分解为更小的子问题，然后合并解D. 直接选择数组中的最大值作为最大字段和（正确答案）。
实验题目 给定由n个整数组成的序列(a1, a2, …, an)，求该序列形如
的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验目的
（1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。
实验内容（包括代码和对应的执行结果截图）
实验代码如下: #include using namespace std;
//蛮力法求解最大字段和问题 int mlf(int a[],int s[][6])
jikka{ int i,j,k=0; for(i=0;i<6;i++) s[i][i]=a[i]; for(i=0;i<6;i++) for(j=i+1;j<6;j++) s[i][j]=s[i][j-1]+a[j]; for(i=0;i<6;i++) for(j=i;j<6;j++) if(s[i][j]>k) k=s[i][j]; if(k<0) k=0; return k; }
//分治法求解最大字段和问题 int MaxSum(int a[],int left,int right) { int sum=0; if(left==right) { //如果序列长度为1，直接求解 if (a[left]>0) sum=a[left]; else sum=0; } else { int center=(left+right)/2; //划分 int leftsum=MaxSum(a,left,center); //对应情况①，递归求解 int rightsum=MaxSum(a,center+1,right); //对应情况②，递归求解 int s1=0; int lefts=0; //以下对应情况③，先求解s1 for (int i=center;i>=left;i--) { lefts+=a[i]; if (lefts>s1) s1=lefts; } int s2=0; int rights=0; //再求解s2 for (int j=center+1;j<=right;j++) { rights+=a[j]; if (rights>s2) s2=rights; } sum=s1+s2; //计算情况③的最大子段和 if (sumif (sum和rightsum中取较大者 } return sum; }
C#如何写⼊和读取Oracle⼤字段如果你的应⽤程序时Oracle数据库，那么将字符串写⼊到⼤字段(Blob)列中是⼀种常见的操作，现作简单介绍：先建⽴⼀个简单的表:create table EMRSIGNINFO(ID VARCHAR2(10),ORIGNDATA BLOB)ORIGNDATA 列为BLOB⼤字段数据类型.然后直接上两个⽅法:View Code//插⼊⼤字段数据public void InsertStringToClob(){System.Data.OracleClient.OracleConnection con = new System.Data.OracleClient.OracleConnection();con.ConnectionString = "Data Source=Orcl; User Id=gctest; Password=his;";//数据库连接串con.Open();using (OracleCommand cmd = new OracleCommand()){mandType = CommandType.Text;cmd.Connection = con;mandText = @"insert into EMRSIGNINFO(ID,ORIGNDATA) values('1',:temp)";OracleParameter param = cmd.Parameters.Add(":temp", OracleType.Blob);param.Direction = ParameterDirection.Input;string strOriginText = @"CzFe3B9mgc1kv3bYldRbMqp9AkCW84EPjBOZZYI+Y0yYgFaDRk4kjmvAuDyF3OAPbCyXoSdzLImG2Y956y/KJV8d3cS0sfjeBLFiFbUXdXfzzgZ23cr44QlMreS9+lIOV0jyd+yX3Spse34rNJwa/aD8i6LTXRCFxfb6Tx1GRj4=CzFe3B9mgc1kv3bYldRbMqp9AkCW84EPjBOZZYI+Y0yYgFaDRk4kjmvAuDyF3OAPbCyXoSdzLImG2Y956 /KJV8d3cS0sfjeBLFiFbUXdXfzzgZ23cr44QlMreS9+lIOV0jyd+yX3Spse34rNJwa/aD8iCzFe3B9mgc1kv3bYldRbMqp9AkCW84EPjBOZZYI+Y0yYgFaDRk4kjmvAuDyF3OAPbCyXoSdzLImG2Y956y/KJV8d3cS0sfjeBLFiFbUXdXfzzgZ23cr44QlMreS9+lIOV0jyd+yX3Spse34rNJwa/aD8i6LTXRCFxfb6Tx1GRj4=6LTXRCFxfb6Tx1GRj4=";param.Value = CompressString(strOriginText);try{cmd.ExecuteNonQuery();}catch (Exception ex){MessageBox.Show(ex.Message);}}con.Close();}//读取⼤字段中存储的字符串public string ReadClobToString(){string strSql = "select * from EMRSIGNINFO where id='1'";string result=string.Empty;System.Data.OracleClient.OracleConnection con = new System.Data.OracleClient.OracleConnection();con.ConnectionString = "Data Source=Orcl; User Id=gctest; Password=his;";con.Open();using (OracleCommand cmd = new OracleCommand()){mandType = CommandType.Text;cmd.Connection = con;mandText = strSql;try{OracleDataReader reader = cmd.ExecuteReader();while (reader.Read()){result = DecompressString((byte[])reader[1]);}}catch (Exception ex){}}con.Close();return result;}针对以上的⼏点说明:1、⼤字段数据列在sql语句中使⽤冒号(:)加⼀个任意名称进⾏占位，如以上第⼀个⽅法中的sql语句中的：temp 。
数据库字段求和
在数据库中，经常需要对某些字段进行求和操作。
这种操作可以用于统计数据、计算总量等方面。
求和操作在SQL语言中也被称为聚合操作。
求和操作可以使用各种SQL语句来实现。
其中，最基本的语句是SELECT SUM()，它可以用于对一个字段进行求和。
例如，可以使用以下语句来计算某个表中所有记录的“销售额”字段之和：
SELECT SUM(销售额) FROM 表名;
如果需要对多个字段进行求和，则可以使用以下语句：
SELECT SUM(字段1 + 字段2 + 字段3) FROM 表名;
该语句将对表中的三个字段进行求和操作。
可以将其修改为任意数量的字段。
还可以使用WHERE子句对要计算的记录进行筛选。
例如，以下语句将对“销售日期”在某个时间段内的记录进行求和操作：
SELECT SUM(销售额) FROM 表名 WHERE 销售日期 BETWEEN '开始时间' AND '结束时间';
需要注意的是，当对一个字段进行求和操作时，如果表中存在null值，则SUM()函数将忽略这些null值。
如果需要将null值视为0进行计算，则可以使用COALESCE()函数来实现：
SELECT SUM(COALESCE(字段名, 0)) FROM 表名;
以上就是数据库字段求和的相关内容。
在实际应用中，根据具体的需求和数据结构，还可以使用其他的SQL语句和函数来实现更复杂
的求和操作。
本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼110专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真指导教师：郝晓丽2018年05月04 日实验一递归与分治算法1.1 实验目的与要求1．进一步熟悉C/C++语言的集成开发环境；2．通过本实验加深对递归与分治策略的理解和运用。
1.2 实验课时2学时1.3 实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。
需要注意的是，分治法使用递归的思想。
划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。
最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。
1.4 实验题目1．上机题目：格雷码构造问题Gray码是一个长度为2n的序列。
序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。
试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。
对于给定的正整数n，格雷码为满足如下条件的一个编码序列。
（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。
（2）序列中无相同的编码。
（3）序列中位置相邻的两个编码恰有一位不同。
2．设计思想：根据格雷码的性质，找到他的规律，可发现，1位是0 1。
两位是00 01 11 10。
三位是000 001 011010 110 111 101 100。
n位是前n-1位的2倍个。
N-1个位前面加0，N-2为倒转再前面再加1。
3．代码设计：}}}int main(){int n;while(cin>>n){get_grad(n);for(int i=0;i<My_grad.size();i++)cout<<My_grad[i]<<endl;My_grad.clear();}return 0;}运行结果：1.5 思考题（1）递归的关键问题在哪里？答：1.递归式，就是如何将原问题划分成子问题。
动态规划之求解最⼤字段和最⼤字段和问题：问题描叙：给定由N个整数组成的序列（a1，a2，...，an），求该序列字段和的最⼤和。
问题很简短，做起来也不是很难，这⾥我们主要为了了解这么⼀种算法思想，然后再尝试求解其他变种问题。
思路：设最⼤字段和为X，X=max(a[i]+···+a[j]),0<=i,j<=n;//为某⼀⼦段之和我们该如何选出这段⼦段：我们设m[j]为从0到j之间的最⼤⼦段和，0<=j<=n;m[j]的含义就是：以a[j]为结束元素的连续数组的最⼤⼦段和。
由此，X=max(m[0]···m[n]);下⾯求m[j]：1.当m[j-1]>0时，⽆论a[j]为何值，m[j]=m[j-1]+a[j];2.当m[j-1]<=0时，⽆论a[j]为何值，m[j]=a[j];⾃⼰想的解释：如果当前和为负数，会影响后续最⼤和，就像你站在地上和桌⼦上最终⾼度不同⼀样，虽为相同⾼度，但产⽣的效果不同，也就是上⼀和为负数时，会影响当前正数发挥最⼤作⽤。
有点⽞学了，**如果⼤佬有更好解释欢迎指点。
**举例：k: 1 2 3 4a: 3 -4 2 10m: 3 -1 2 12代码：int m[n+1];b[1]=a[1];int maxSum=a[1];for(int i=2;i<=n;i++){if(m[i-1]<=0){m[i]=a[i];}else{m[i]=m[i-1]+a[i];}maxSum=max(m[i],maxSum);}最⼤⼦段和扩展：给定⼀个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最⼤的⼦矩阵。
返回⼀个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表⼦矩阵左上⾓的⾏号和列号，r2, c2 分别代表右下⾓的⾏号和列号。
若有多个满⾜条件的⼦矩阵，返回任意⼀个均可。
