golang求连续子数组的最大和实例

2024-10-20 12:49:40

问题描述：

给定一个数组 array[1, 4, -5, 9, 8, 3, -6]，在这个数字中有多个子数组，子数组和最大的应该是：[9, 8, 3]，输出20，再比如数组为[1, -2, 3, 10, -4, 7, 2, -5]，和最大的子数组为[3, 10, -4, 7, 2]，输出18。

代码如下：

package main
import (
 "fmt"
)
func getMaxSum(arr []int) int {
 var sum, maxSum int
 for i := 0; i < len(arr); i++ {
 sum = 0
 for j := i; j < len(arr); j++ {
  sum += arr[j]
  if sum > maxSum {
  maxSum = sum
  }
 }
 }
 return maxSum
}
func main() {
 var arr []int
 arr = []int{1, -2, 3, 10, -4, 7, 2, -5}
 fmt.Println(getMaxSum(arr))
}

补充：go语言实现求一个无序数组，最大连续数量

思路：

把每个元素当作一个中心元素

进行左右延伸

package main
import (
  "fmt"
)
func main() {
  array := []int{5,2,3,2,3,10,1,12,4}
  myMap := make(map[int]int)
  for _,value := range array {
    myMap[value] = 1
  }
  longest := 0
  for _,i := range array{
    length := 1
    for j:=i-1; myMap[j] == 1; j-- {
      delete(myMap, j)
      length++
    }
    for j :=i+1;myMap[j] == 1 ;j++ {
      delete(myMap,j)
      length++
    }
    if(length > longest){
      longest = length
    }
  }
  fmt.Println(longest)
}

以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。如有错误或未考虑完全的地方，望不吝赐教。

Golang中的Slice与数组及区别详解

在golang中有数组和Slice两种数据结构,Slice是基于数组的实现,是长度动态不固定的数据结构,本质上是一个对数组字序列的引用,提供了对数组的轻量级访问.那么我们今天就给大家详细介绍下Golang中的Slice与数组, 1.Golang中的数组数组是一种具有固定长度的基本数据结构,在golang中与C语言一样数组一旦创建了它的长度就不允许改变,数组的空余位置用0填补,不允许数组越界. 数组的一些基本操作: 1.创建数组: func main() { var arr1 = [.
Golang数组的传递详解

概念介绍数组与切片数组是具有相同唯一类型的一组已编号且长度固定的数据项序列.数组长度最大为2Gb,它是值类型.切片是对数组一个连续片段的引用,所以切片是一个引用类型. 按值传递和按引用传递 Go语言中函数的参数有两种传递方式,按值传递和按引用传递.Go默认使用按值传递来传递参数,也就是传递参数的副本.在函数中对副本的值进行更改操作时,不会影响到原来的变量. 按引用传递其实也可以称作"按值传递",只不过该副本是一个地址的拷贝,通过它可以修改这个值所指向的地址上的值. Go语言中,在函
简单谈谈Golang中的字符串与字节数组

前言字符串是 Go 语言中最常用的基础数据类型之一,虽然字符串往往都被看做是一个整体,但是实际上字符串是一片连续的内存空间,我们也可以将它理解成一个由字符组成的数组,Go 语言中另外一个与字符串关系非常密切的类型就是字节(Byte)了,相信各位读者也都非常了解,这里也就不展开介绍. 我们在这一节中就会详细介绍这两种基本类型的实现原理以及它们的转换关系,但是这里还是会将介绍的重点主要放在字符串上,因为这是我们接触最多的一种基本类型并且后者就是一个简单的 uint8 类型,所以会给予 string
golang实现整型和字节数组之间的转换操作

我就废话不多说了,大家还是直接看代码吧~ //isSymbol表示有无符号 func BytesToInt(b []byte, isSymbol bool) (int, error){ if isSymbol { return bytesToIntS(b) } return bytesToIntU(b) } //字节数(大端)组转成int(无符号的) func bytesToIntU(b []byte) (int, error) { if len(b) == 3 { b = append([]b
golang求连续子数组的最大和实例

问题描述: 给定一个数组 array[1, 4, -5, 9, 8, 3, -6],在这个数字中有多个子数组,子数组和最大的应该是:[9, 8, 3],输出20,再比如数组为[1, -2, 3, 10, -4, 7, 2, -5],和最大的子数组为[3, 10, -4, 7, 2],输出18. 代码如下: package main import ( "fmt" ) func getMaxSum(arr []int) int { var sum, maxSum int for i :=
PHP实现求连续子数组最大和问题2种解决方法

本文实例讲述了PHP实现求连续子数组最大和问题2种解决方法.分享给大家供大家参考,具体如下: 问题描述求子数组的最大和题目描述: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值.要求时间复杂度为O(n). 关于连续子数组最大和这个问题,有两种解法,一种是动态规划解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0];
Python语言描述连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值
python求最大连续子数组的和

抛出问题: 求一数组如 l = [0, 1, 2, 3, -4, 5, -6],求该数组的最大连续子数组的和如结果为[0,1,2,3,-4,5] 的和为7 问题分析: 这个问题很简单,直接暴力法,上代码. # -*- coding:utf-8 -*- # 日期:2018/6/9 7:46 # Author:小鼠标 # 最大连续子数组的和 l = [0, 1, 2, 3, -4, 5, -6] # 暴力求解 def violence(l = []): maxVal = 0 x,y=0,0 for
求子数组最大和的实例代码

题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为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
Java实现求子数组和的最大值算法示例

本文实例讲述了Java实现求子数组和的最大值算法.分享给大家供大家参考,具体如下: 一般C和C++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感. 题目: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值. 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18. 实现代码: package arrDe
求子数组最大和的解决方法详解

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

给定一组数,有正有负,求连续的几个数之和的最大值?并求出是从第几个数开始,第几个数结束?如果有多个序列可组成相同的最大值,则选取最开始的一个序列.(注:这两天看<编程之美>,发现2.14节,求数组的子数组之和的最大值,跟这个题十分相似,但是没有要求求出开始喝结束的位置,只要求求出最大值,解题思路跟下面的代码相似,但只用了两个变量,没有用数组,做到时间复杂度O(n),空间复杂度O(1))用程序设计实现.我实现了一种方法,跟大家分享一下,如果朋友你有更好的方法来解决这个问题,希望你能回复,与大家分
C++实现LeetCode(209.最短子数组之和)

[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和 Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead. Example: Input: s = 7, num
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

golang求连续子数组的最大和实例

问题描述：

思路：

相关推荐

随机推荐