精华内容
下载资源
问答
  • 连续子数组的最小和

    千次阅读 2018-07-23 18:05:00
    连续子数组的最大 连续子数组的最大的问题相信大家都不会陌生了,代码如下: int MaxSubSum(int arr[],int len) { int i; int MaxSum = 0; int ThisSum= 0; for(i=0;i<len;i++) { ThisSum+= arr[i]; ...

    连续子数组的最大和

    连续子数组的最大和的问题相信大家都不会陌生了,代码如下:

    int MaxSubSum(int arr[],int len)
    {
        int i;
        int MaxSum = 0;
        int ThisSum= 0;
        for(i=0;i<len;i++)
        {
            ThisSum+= arr[i];
            if(ThisSum > MaxSum)
            {
                MaxSum = ThisSum;
            } 
             /*如果累加和出现小于0的情况,
               则和最大的子序列肯定不可能包含前面的元素,
               这时将累加和置0,从下个元素重新开始累加  */
            else if(ThisSum< 0)
            {
                ThisSum = 0;
            }
        }
        return MaxSum;
    }

    连续子数组的最小和

    连续子数组的最小和,网上讨论的比较少,这里给出我自己的代码:

    经过一些吐槽,重新编写这段代码:

    int MinSum(int a[],int len)
    {
    
        for(int i  = 0;i<len;i++)
        {
            a[i]=a[i]*(-1);//
        }
        return (-1)*MaxSubSum(a,len);
    
    
    }
    int main()
    {
        int a[7]={3, -4, 2, -3, -1, 7, -5};
        int minSum = MinSum(a,7);
        return minSum;
    
    }

    经过几组测试用例,还可以,如果有问题,希望指出。

    展开全文
  • JAVA算法:求给定数组中连续子数组的最小和 求给定数组中连续子数组的最小和。 package com.bean.algorithm.basic; public class SmallestSumContiguousSubarray { static int smallestSumSubarr(int arr[], ...

    JAVA算法:求给定数组中连续子数组的最小和

    求给定数组中连续子数组的最小和。

    package com.bean.algorithm.basic;
    
    public class SmallestSumContiguousSubarray {
    
    	static int smallestSumSubarr(int arr[], int n) {
    
    		int min_ending_here = 2147483647;
    
    		// to store the minimum value encountered
    		// so far
    		int min_so_far = 2147483647;
    
    		for (int i = 0; i < n; i++) {
    
    			// if min_ending_here > 0, then it could
    			// not possibly contribute to the
    			// minimum sum further
    			if (min_ending_here > 0)
    				min_ending_here = arr[i];
    
    			// else add the value arr[i] to
    			// min_ending_here
    			else
    				min_ending_here += arr[i];
    
    			// update min_so_far
    			min_so_far = Math.min(min_so_far, min_ending_here);
    		}
    
    		return min_so_far;
    	}
    
    
    	public static void main(String[] args) {
    
    		int arr[] = { 3, -4, 2, -3, -1, 7, -5 };
    		int n = arr.length;
    
    		System.out.print("Smallest sum: " + smallestSumSubarr(arr, n));
    	}
    }
    

    程序运行结果:

    Smallest sum: -6

     

    展开全文
  • 动态规划:相信大家都做过求一个数组中连续子数组的最大,解法是定义dp[i]表示以i结尾的最大子数组,其状态转换方程为dp[i] = max(dp[i-1]+A[i],A[i])。但是本题的关键在于数组是一个环形数组,解决办法是分两种...

    动态规划:

    求一个数组中连续子数组的最大和,解法是定义dp[i]表示以i结尾的最大子数组和,其状态转换方程为dp[i] = max(dp[i-1]+A[i],A[i])。本题数组是一个环形数组,解决办法是分两种情况考虑:(1)不超过边界的子数组的最大和,解决办法和上面一样;(2)超过边界的子数组的最大和,另外开辟一个数组记录子数组最小的和,然后用整个数组的和减去最小数组和中最小的值,即为跨越边界的子数组最大和。(3)负数依题而定

    int maxSubarraySumCircular(int arr[])
    {
        int total=0;
        vector<int>dpMax(N);
        vector<int>dpMin(N);
        dpMax[0]=dpMin[0]=arr[0];
        total+=arr[0];
        //分析,最大值为单个序列最大或是首尾相连(总和减去最小值),取两者最大
        for(int i=1;i<N;i++){
            total+=arr[i];
            dpMax[i]=max(dpMax[i-1]+arr[i],arr[i]);
            dpMin[i]=min(dpMin[i-1]+arr[i],arr[i]);
            if(Max<dpMax[i]) Max=dpMax[i];
            if(Min>dpMin[i]) Min=dpMin[i];
        }
        res = max(Max,total-Min);
    }

     

    展开全文
  • 本文是《剑指Offer》系列(JavaScript版)的第一篇,题目是“连续子数组的最大和或最小和”。 话不多说,开始“打怪”修炼... 一、理解题目 以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组...

    前言

    本文是《剑指Offer》系列(JavaScript版)的第一篇,题目是“连续子数组的最大和或最小和”。

    话不多说,开始“打怪”修炼…

    一、理解题目

    以“连续子数组的最大和”为例,相当于我们在数组中,计算连续的子数组的和,找寻最大值。如在数组[3, -2, 1, 2, 4, -6, 5]中连续子数组的最大和为:3 + (-2) + 1 + 2 + 4 = 8

    输入:[3, -2, 1, 2, 4, -6, 5]
    输出:8
    

    一定要准确的理解题意,如不是特别明确,建议与面试官再次沟通确认,避免需求与实现不一致的情况。

    二、解决方案

    连续子数组的最大和

    这道面试题有几种解决方案呢?可能在很多个同学的脑海里会出现这样的一种方案:

    1. 求连续子数组组合方案:

    将数组中的元素进行连续子数组的组合,每一种组合计算出一个值,依次比较后取出最大值。那这种方式是可以肯定是可以最终的效果的,But这么处理的话,会有多少种组合方案呢?

    以数组 [1, -1, 2, -3, 5]为例:
    	连续子数组有:N + (N-1) + (N-2)...  +  1 = n*(n+1) / 2
    

    随着数组长度N的值越大,组合数量肯定是越大!同时在获取阶乘后,还需要再次进行一次最大值得比较。

    划重点:

    此方案虽可以实现最终的效果,但是确实十分不可取的!

    2. 最优解方案

    在面试时面试题除了固定的套路和算法外,要多尝试逻辑思维的转变…

    技术方案:
    	1. 初始化两个变量:sum(连续子数组的累加和)、max(最大值)
    	2. 遍历数组元素,考虑sum的情况: 
    		sum >= 0,将当前元素的值进行累加
    		sum < 0,注意,sum的值为负值,不管当前的元素值是什么,累加sum(负数)肯定值最终会变小的,所以此刻,要重新对sum进行赋值操作
    	3. 每次遍历时,都要比较sum和max的大小, 如果 sum > max,进行赋值max = sum
    	4. 返回最终的结果max
    

    接下来,我们来看下代码的实现:

    /**
     * getGreatestSumOfSubArray()
     * @description 获取连续子数组中最大和
     * @param Array arr 指定的数组
     * @returns Number sum 最大和
    */
    function getGreatestSumOfSubArray (arr) {
      // 容错边界处理
      if (!Array.isArray(arr) || arr.length === 0) {
        return 0
      }
    
      // 解构,初始获取数组的第一个元素值
      // 注意:一定不能把sum和max设置初始化为0,必须要考虑数组元素中全部为负数的情况
      let [ sum ] = arr
      let [ max ] = arr
      
      let len = arr.length
      for (let i = 1; i < len; i++) {
        // 如果当前sum累加 < 0,重新初始化当前元素值;否则执行累加
        if (sum < 0) {
          sum = arr[i]
        } else {
          sum += arr[i]
        }
    
        // 比较累加和与最大值
        if (sum > max) {
          max = sum
        }
      }
      
      return max
    }
    
    // 调用
    let max = getGreatestSumOfSubArray([3, -2, 1, 2, 4, -6, 5])
    console.log(max) // 8
    

    OK,这样我们就实现了需求,小朋友,你还有问号吗?

    连续子数组的最小和

    “连续子数组的最小和” 这个需求的实现原理和“连续子数组的最大和”的实现基本是一致的,唯一的区别点为:当sum的值 > 0为正数时,累加就无意义了,需要重新赋值为当前值。我们来看下代码的实现

    /**
     * getLeastSumOfSubArray()
     * @description 获取连续子数组的最小和
     * @param Array arr 指定的数组
     * @returns Number min 最小和
    */
    function getLeastSumOfSubArray (arr) {
      if (!Array.isArray(arr) || arr.length === 0) {
        return 0
      }
    
      // 初始化
      let [ sum ] = arr
      let [ min ] = arr
    
      // 遍历数组元素,如果sum是一个正数,累加就无意义,重新赋值为当前项;
      let len = arr.length
      for (let i = 1; i < len; i++) {
        if (sum > 0) {
          sum = arr[i]
        } else {
          sum += arr[i]
        }
        if (sum < min) {
          min = sum
        }
      }
    
      return min
    }
    
    let min = getLeastSumOfSubArray([-1, -2, 3, 2, -4, -8])
    console.log(min) // -12 = (-4) + (-8)
    

    这个了解了不…

    后记

    以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得点赞收藏呦,关注胡哥有话说,学习前端不迷路,欢迎多多留言交流…

    胡哥有话说,一个有技术,有情怀的胡哥!现任京东前端攻城狮一枚。

    胡哥有话说,专注于大前端技术领域,分享前端系统架构,框架实现原理,最新最高效的技术实践!

    展开全文
  • import java.util.Scanner; /** * @program: entrance_exam ... * 如{6,-3,-2,7,-15,1,2,2}连续子向量最大为8,最小乘积的连续子数组为6*(-3)*(-2)*7*(-15)*1*2*2 * @author: TAO * @...
  • JAVA算法:子数组的最小和 给定一个整数数组A,找到min(B)的总和,其中B的范围为A的每个(连续)子数组。 例如:给定数组 A为 [3,1,2,4] 输出:17 解释:数组A的子数组为: [3],[1],[2],[4],[3,1],[1,2],[2,...
  • 一个连续的数组,分成m个连续子数组,求各个子数组的和的最大值最小 这是在freewheels笔试的第一个编程题,我还是没搞懂呀 参考一下别人的代码: #include <iostream> #include <ctime> using namespace...
  • 求一个数组中和最小的连续子数组

    千次阅读 2015-04-12 01:18:52
    #include #define MAX_LENGTH 10 int main() { int a[MAX_LENGTH]={1,2,3,-2,4,-6,-8,5,3,1}; ... //begend分别为子数组中首末元素下标,min为无穷大数 beg=end=tmp=0; for(i=0;
  • 给定一个含有 n 个正整数数组一个正整数 s ,找出该数组中满足其 ≥ s 长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4...
  • 连续子数组的最大

    2017-09-08 10:37:01
    题目描述:输入一个整形数组,数组里面有正数也有负数,数组中一个或连续的多个整数构成一个子数组,求所有子数组的和的最大值,要求时间复杂度为O(n)。 思路分析: 代码分析:#include #include using ...
  • 给定一个含有 n 个正整数数组一个正整数 s ,找出该数组中满足其 ≥ s 长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。 (1) 暴力破解法: 1、从头遍历数组,从当前数组元素...
  • 文章目录1、最小的K个数2、连续子数组的最大 1、最小的K个数 描述:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则这个最小的4个数字为1,2,3,4。 思路:或用堆 测试...
  • 最小的K个数 输入n个整数,找出其中最小的K个...遍历数组,每次找到最小的取出来,完成k次遍历,找出最小的k个数 代码 import java.util.ArrayList; public class jzo29 { public ArrayList<Integer> GetLe...
  • 连续子数组的最大题目分析代码 题目 输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 ...
  • 给定一个含有 n 个正整数数组一个正整数 s ,找出该数组中满足其 ≥ s 长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4...
  • 给定一个含有 n 个正整数数组一个正整数 s ,找出该数组中满足其 ≥ s 长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 ...
  • 找出该数组中满足其 ≥ target 长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件子数组,返回 0 滑动窗口 class Solution { public: /* 滑动窗口 */ ...
  • 给定一个含有n个正整数数组一个正整数s ,找出该数组中满足其≥ s长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组[4,3]...
  • 连续子数组的和的最大值、最小值以及和的绝对值的最大值、最小值 标签: 子数组最小和绝对值最大和 http://blog.csdn.net/zuijinhaoma8/article/details/45290145 2015-04-26 17:30 527人阅读 评论(1...
  • 解析:动态规划思想,保存两个临时变量maxProductminProduct,这两个临时变量分别存储,以当前位置结尾的连续子数组的最大乘积和最小乘积。int maxProduct(vector& nums) { int maxRes = nums[0]; int maxPro
  • 求数组的连续子数组的最大值 输入一个N个元素的整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个。求所有子数组的和的最大值。 例如输入的数组为-9 -3 -2...
  • 复杂链表的复制、字符串的排列、数组中出现次数超过一半的数字、最小的K个数、连续子数组的最大复杂链表的复制题目描述C++代码字符串的排列题目描述C++代码数组中出现次数超过一半的数字题目描述C++代码最小的K个...
  • 剑指offer——面试题31:连续子数组的最大 讲道理是这是标准的动态规划的题目,可是思路未完全想好。 min_element(iterator,iterator)max_element(iterator,iterator),迭代器的指示范围是闭开区间,返回值...
  • 29、最小的K个数 时间限制:1秒 空间限制:32768K 热度指数:511475 本题知识点: 数组 高级算法 题目描述:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 ...
  • s ,找出该数组中满足其 ≥ s 长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 * 示例:  * 输入: s = 7, nums = [2,3,1,2,4,3] * 输出: 2 * 解释: 子数组 [4,3] 是该条件下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,173
精华内容 469
关键字:

连续子数组的最小和