求子数组最大和的实例代码
题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为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[i],dp[i-1]+arr[i]};
代码如下;
#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int res(int* arr, int len){
//学到一个定义最小数的方法:)
int max = -(1<<31);
int i;
for(i=1;i<len;i++){
arr[i] = max(arr[i],arr[i-1]+arr[i]);
if(max < arr[i]) max = arr[i];
}
return max;
}
int main(){
int arr[] = {1,-2,3,10,-4,7,2,-5};
printf("%d\n",res(arr,8));
return 0;
}
相关推荐
-
求PHP数组最大值,最小值的代码
复制代码 代码如下: <?php $fruits = array("155::vbscript::http://www.jb51.net/list/list_114_1.htm", "1::javascript::http://www.jb51.net/list/list_3_1.htm", "2::正则表达式::http://www.jb51.net/list/list_6_1.htm", "3::服务器常用软件::http:/
-
获取数组中最大最小值方法js代码(自写)
现在获取数组中最大最小值用的越来越多了,于是乎我编了个方法供大家使用.代码如下,若有问题可以与我联系,咱们一起学习一起进步. 复制代码 代码如下: function getMaximin (arr,maximin) { if (maximin == "max") { return Math.max.apply(Math, arr); }else if (maximin == "min") { return Math.min.apply(Math, arr); } }
-
求子数组最大和的解决方法详解
题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18.如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和.不过非常遗憾的是,由于长度为n的数组有O(n2)个子数组:而且求一个长度为n的数组的和的时间复杂度为O(n).因此这种思路的时间
-
javascript的原生方法获取数组中的最大(最小)值
获取一个数组中的最大(最小)值的最简单的方法,就是对数组进行一次遍历,通过比较,找到其最大(最小)值.但是其实在javascript的原生方法中,已经提供了一些快捷方法,可以实现此功能. 1 Array.prototype.sort 复制代码 代码如下: var a = [7,3,4,6,10]; a.sort(function(a,b){ return (a-b);}) 注意,sort里的比较函数是一定要传入的,如果不传此函数的话,a.sort()的结果是[10,3,4,6,7]; 2 Mat
-
求子数组最大和的实例代码
题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为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
-
PHP实现求连续子数组最大和问题2种解决方法
本文实例讲述了PHP实现求连续子数组最大和问题2种解决方法.分享给大家供大家参考,具体如下: 问题描述 求子数组的最大和 题目描述: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值.要求时间复杂度为O(n). 关于连续子数组最大和这个问题,有两种解法,一种是动态规划 解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0];
-
Java实现求子数组和的最大值算法示例
本文实例讲述了Java实现求子数组和的最大值算法.分享给大家供大家参考,具体如下: 一般C和C++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感. 题目: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值. 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18. 实现代码: package arrDe
-
python如何求数组连续最大和的示例代码
题目描述: 一个有 n 个元素的数组,这 n 个元素既可以是正数也可以是负数,数组中连续的一个或多个元素可以组成一个连续的子数组,一个数组可能有多个这种连续的子数组,求子数组的最大值.例如,对于数组 [1,-2,4,8,-4,7,-1,-5] 而言,其最大和的子数组为 [4,8,-4,7],最大值为 15. 方法: 蛮力法 重复利用已经计算的子数组和 动态规划 优化的动态规划 1.蛮力法 找出所有的子数组,然后求出子数组的和,在所有子数组的和中取最大值. 代码实现: #!/usr/bin/env
-
Java中求最大值的4种方法实例代码
前言 本文主要给大家分享了关于java求最大值的4中方法,文中给出了完整的示例代码,下面话不多少了,来一起看看吧 示例代码: /** *@author Prannt *求最大值(或最小值) *本例以int数据类型为例,可指定其他数据类型 */ //方法一:直接法,求最小值类似 public class Deno05ArrayMax { public static void main(String[] args) { //数据类型可指定 int [] array = {5,15,20,30,100
-
javascript 三组文字间隙滚动实例代码
三组文字间隙滚动 *{font-size:12px;} #scrollBox2{width:150px; height:64px; line-height:22px; overflow:hidden; background-color:#eee;} 国家 汇率名称 今日汇率 美元USD ŀ.775% 港币HKD ŀ.75% 英镑GBP ŀ.50% 欧元EUR ŀ.25% 日元JPY ŀ.01% window.onload=function(){ new Marquee( "scrollBox2&
-
python求两个时间的时间差(实例代码)
我们在用python进行分析的时候,可能会碰到计算两个日期的时间差.下面为大家介绍一下如何计算两个时间的时间差: from dateutil.parser import parse a = parse('2017-10-01/12:12:12') b = parse('2013-3-4/10:10:10') (a-b).days (a-b).seconds (a-b).total_seconds() 为大家介绍上面三种函数的含义: 1.days:来获取时间差的天数 2.seconds:来获取时间
-
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
-
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 :=
随机推荐
- seajs中最常用的7个功能、配置示例
- asp.net mvc 从数据库中读取图片的实现代码
- PHP实现的一个保存远程文件到本地的函数分享
- 华众HZHOST虚拟主机管理系统服务器IP更换详细步骤说明
- ASP.NET插件uploadify批量上传文件完整使用教程
- Xenserver迁移所有虚拟机到VMware vSphere 6.0
- javascript获取设置div的高度和宽度兼容任何浏览器
- javascript 用记忆函数快速计算递归函数
- php使用Cookie实现和用户会话的方法
- c#异步发送邮件的类
- mysql数据库重命名语句分享
- JavaScript制作的可折叠弹出式菜单示例
- 点击地图div上的按钮实现对地图数据的入库操作
- 经典语句集锦
- 如何在Python函数执行前后增加额外的行为
- jQuery根据ID、CLASS、等获取对象的实例
- JavaScript之HTMLCollection接口代码
- 深入分析Javascript跨域问题
- 一段好玩的JavaScript代码
- JVM 参数配置详细介绍