求最大子数组之和的方法解析（2种可选）

问题描述：一个有n个元素的数组，这n个元素可以是正数也可以是负数，求最大子数组的和。

方法1：蛮力法

思路：最简单也是最容易想到的方法就是找出所有子数组，然后求所有子数组的和，在所有子数组的和中取最大值。

/**
  * 方法1（蛮力法）：两次循环求最大子数组之和
  */
 public static int maxSubArray1(int[] a){
  int i,j;
  int ThisSum=0;
  int MaxSum=0;
  for (i = 0; i < a.length; i++) {
   ThisSum=a[i];
   for(j=i+1;j<a.length;j++){
    ThisSum+=a[j];
    if(ThisSum>MaxSum){
     MaxSum=ThisSum;
    }
   }
  }
  return MaxSum;
 }

方法2：优化的动态规划

思路：首先可以根据数组的最后一个元素a[n-1]与最大子数组的关系分为以下三种情况：

1) 最大子数组包含a[n-1]，即以a[n-1]结尾。

2) a[n-1]单独构成最大子数组。

3) 最大子数组不包含a[n-1]，那么求a[1,...,n-1]的最大子数组可以转换为求a[1,...,n-2]的最大子数组。

通过上述分析可以得出如下结论：假设已经计算出(a[0],...a[i-1])最大的一段数组和为All[i-1]，同时也计算出(a[0],...a[i-1])中包含a[i-1]的最大的一段数组和为End[i-1]，

则可以得出如下关系：All[i-1]=max{a[i-1],End[i-1],All[i-1]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置，终止位置的问题)

/**
  * 方法2：优化的动态规划方法
  * nEnd就是通过“数组依次相加加到a[i]，然后与a[i]做比较”得来的，保存较大的。因为如果前面的数加到a[i]
  * 还没有a[i]本身大，那么前面的数也就对最大子数组和没有贡献。厉害
  * nAll就是记录一下之前的新得到的nEnd和自身之前谁更大
  */
 public static int max(int m,int n){
  return m>n?m:n;
 }
 public static int maxSubArray2(int[] a){
  int nAll=a[0];//有n个数字数组的最大子数组之和
  int nEnd=a[0];//有n个数字数组包含最后一个元素的子数组的最大和
  for (int i = 1; i < a.length; i++) {
   nEnd=max(nEnd+a[i],a[i]);
   nAll=max(nEnd, nAll);
  }
  return nAll;
 }
 private static int begin=0;
 private static int end=0;
 /**
  * 求出最大子数组的开始begin，结尾end，以及整个子数组
  */
 public static int maxSubArray3(int[] a){
  int maxSum=Integer.MIN_VALUE;
  int nSum=0;
  int nStart=0;
  for (int i = 0; i < a.length; i++) {
   if(nSum<0){
    nSum=a[i];
    nStart=i;
   }
   else{
    nSum+=a[i];
   }
   if(nSum>maxSum){
    maxSum=nSum;
    begin=nStart;
    end=i;
   }
  }
  return maxSum;
 }

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我们！

赞 (0)

相关推荐

  • 求子数组最大和的解决方法详解

    题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18.如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和.不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组:而且求一个长度为n的数组的和的时间复杂度为O(n).因此这种思路的时间

  • php数组函数序列之array_sum() - 计算数组元素值之和

    array_sum()定义和用法 array_sum() 函数返回数组中所有值的总和. 如果所有值都是整数,则返回一个整数值.如果其中有一个或多个值是浮点数,则返回浮点数. PHP 4.2.1 之前的版本修改了传入的数组本身,将其中的字符串值转换成数值(大多数情况下都转换成了零,根据具体制而定). 语法 array_sum(array) 参数 描述 array 必需.规定输入的数组. 例子1 复制代码 代码如下: <?php $a=array(0=>"5",1=>&q

  • C语言求连续最大子数组和的方法

    本文实例讲述了C语言求连续最大子数组和的方法,是非常实用的技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> using namespace std; int array[] = {1, -2, 3, 10, -4, 7, 2, -5}; //int array[] = {-10, -1, -2, -3, -4, -5}; const int size = sizeof array / sizeof *array; int maxSubArray(int

  • 求子数组最大和的实例代码

    题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18. 找到状态转移方程,dp[i]表示前i个数中,包含i的子数组的最大和.要么第i个数自己最大,要么他要和包含i-1的子数组最大和(即dp[i-1])联合在一起.即dp[i] = max{arr

  • 求最大子数组之和的方法解析（2种可选）

    问题描述:一个有n个元素的数组,这n个元素可以是正数也可以是负数,求最大子数组的和. 方法1:蛮力法 思路:最简单也是最容易想到的方法就是找出所有子数组,然后求所有子数组的和,在所有子数组的和中取最大值. /** * 方法1(蛮力法):两次循环求最大子数组之和 */ public static int maxSubArray1(int[] a){ int i,j; int ThisSum=0; int MaxSum=0; for (i = 0; i < a.length; i++) { This

  • C++实现LeetCode(152.求最大子数组乘积)

    [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has

  • Java数组扩容实现方法解析

    这篇文章主要介绍了Java数组扩容实现方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 第一种 int[] arr2=new int[arr1.length*2] //新数组的长度 第二种 int[] arr2=java.util.Arrays.copyOf(原数组名,新数组的长度); 第三种 int[] arr2=new int[arr1.length*2] System.arraycopy(原数组名,起始下标,新数组名,起始下标,复制

  • Python实现求两个数组交集的方法示例

    本文实例讲述了Python实现求两个数组交集的方法.分享给大家供大家参考,具体如下: 一.题目 给定两个数组,编写一个函数来计算它们的交集. 例1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 例2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9] 说明: 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致 我们可以不考虑输出结果的顺序 二.解法 首先把两个数组都排序,然后两个数

  • python分治法求二维数组局部峰值方法

    题目的意思大致是在一个n*m的二维数组中,找到一个局部峰值.峰值要求大于相邻的四个元素(数组边界以外视为负无穷),比如最后我们找到峰值A[j][i],则有A[j][i] > A[j+1][i] && A[j][i] > A[j-1][i] && A[j][i] > A[j][i+1] && A[j][i] > A[j][i-1].返回该峰值的坐标和值. 当然,最简单直接的方法就是遍历所有数组元素,判断是否为峰值,时间复杂度为O(n^2

  • Javascript 数组去重的方法（四种）详解及实例代码

     Javascript 数组去重的四种方法 四种算法来实现这个目的: 第一种方法: Array.prototype.unique1 = function () { var n = []; //一个新的临时数组 for (var i = 0; i < this.length; i++) //遍历当前数组 { //如果当前数组的第i已经保存进了临时数组,那么跳过, //否则把当前项push到临时数组里面 if (n.indexOf(this[i]) == -1) n.push(this[i]); }

  • C++实现LeetCode(53.最大子数组)

    [LeetCode] 53. Maximum Subarray 最大子数组 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1]

  • JS实现求数组起始项到终止项之和的方法【基于数组扩展函数】

    JS实现求数组起始项到终止项之和的方法【基于数组扩展函数】

    本文实例讲述了JS实现求数组起始项到终止项之和的方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>JS求数组之和</title> </head> <body> <script > Array.prototype.sum= funct

  • php str_getcsv把字符串解析为数组的实现方法

    php根据定界符把字符串解析为数组一般使用explode方法实现 例如:使用","为定界符解析字符串为数组 <?php $str = '1,2,3'; $arr = explode(',', $str); print_r($arr); ?> 输出: Array ( [0] => 1 [1] => 2 [2] => 3 ) 但对于一些较复杂的字符串,例如csv格式,使用explode不能得出想要的结果,而使用正则较麻烦. 例如: <?php $str

随机推荐