PHP实现求连续子数组最大和问题2种解决方法

本文实例讲述了PHP实现求连续子数组最大和问题2种解决方法。分享给大家供大家参考，具体如下：

问题描述

求子数组的最大和

题目描述：

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

关于连续子数组最大和这个问题，有两种解法，一种是动态规划

解法如下：

function getMaxSubSum($arr){
  $curSum = $arr[0];
  $maxSum = $arr[0];
  for($i = 1; $i < count($arr); $i++){
    if($curSum > 0) $curSum += $arr[$i];
    else $curSum = $arr[$i];
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  return $maxSum;
}

还有一种是扫描法

function getMaxSubSum($arr){
  $curSum = 0;
  $maxSum = 0;
  for($i = 0; $i < count($arr); $i++ ){
    $curSum += $arr[$i];
    if($curSum <= 0) $curSum = 0;
    if($curSum > $maxSum) $maxSum = $curSum;
  }
  if($maxSum == 0){
    $maxSum = $arr[0];
    for($i = 1; $i < count($arr); $i++){
      if($maxSum < $arr[$i] ) $maxSum = $arr[$i];
    }
  }
  return $maxSum;
}

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》、《php字符串(string)用法总结》、《php常用函数与技巧总结》、《PHP错误与异常处理方法总结》、《PHP基本语法入门教程》、《php面向对象程序设计入门教程》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

赞 (0)

相关推荐

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

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

  • PHP判断一个数组是另一个数组子集的方法详解

    PHP判断一个数组是另一个数组子集的方法详解

    本文实例讲述了PHP判断一个数组是另一个数组子集的方法.分享给大家供大家参考,具体如下: 前言 今天完成一个算法的过程中,有几个需求模块,其中就有判断$a数组是否是$b数组的子集,可能最近我写c比较多,直接就用for循环实现了,但是感觉代码量比较大,不够优雅!在qq群里集思广益了一下,发现很多php提供的系统功能函数都是可以供调用的,这里记录一下 需求 最少的时间复杂度判断$a数组是否是$b数组的子集 // 快速的判断$a数组是否是$b数组的子集 $a = array(135,138); $b

  • php计算数组相同值出现次数的代码(array_count_values)

    php计算数组相同值出现次数,可以使用php自带函数array_count_values : 说明 array array_count_values ( array $input )array_count_values() 返回一个数组,该数组用 input 数组中的值作为键名,该值在 input 数组中出现的次数作为值. array_count_values() 例子 复制代码 代码如下: <?php $array = array(1, "hello", 1, "wo

  • php计算多维数组中所有值总和的方法

    本文实例讲述了php计算多维数组中所有值总和的方法.分享给大家供大家参考.具体实现方法如下: php 内置函数 array_sum() 函数返回数组中所有值的总和,只能返回一维数组的总和: 计算多维数组所有值的和就要自定义函数了: function get_sum($array) { $num = 0; foreach($array as $k => $v) { if(is_array($v)) { $num += get_sum($v); } } return $num + array_sum

  • PHP计算数组中值的和与乘积的方法(array_sum与array_product函数)

    本文实例讲述了PHP计算数组中值的和与乘积的方法.分享给大家供大家参考,具体如下: 一.概述: array_sum() 函数用于计算数组中所有值的和. array_product() 函数用于计算数组中所有值的乘积. 二.使用示例: array_sum() PHP array_sum() 函数用于计算数组中所有值的和,以整数或浮点数返回计算结果,非数字的单元将视作 0 . 语法: number array_sum( array array ) 例子: <?php $arr_a = array(1

  • php求正负数数组中连续元素最大值示例

    php实现正负数数组最大子序列,要求给出数组,该数组由正负数字组成,找出该数组中连续元素组成的子数组的最大值.这其实得算是个背包变种吧. 复制代码 代码如下: <?php$list = array(1,-3,-5,-7,8,9,-11,5); $cur = 0;$term = 0;$res = 0;$begin = 0; foreach($list as $k => $v){ $cur += $v; if($cur < 0){  $cur = 0;  $begin = $k + 1; }

  • php常用数组array函数实例总结【赋值,拆分,合并,计算,添加,删除,查询,判断,排序】

    本文实例总结了php常用数组array函数.分享给大家供大家参考,具体如下: array_combine 功能:用一个数组的值作为新数组的键名,另一个数组的值作为新数组的值 案例: <?php $a = array("one","two","three"); $b = array("一","二","三"); $c = array_combine($a,$b); print_r($c

  • PHP数组操作实例分析【添加,删除,计算,反转,排序,查找等】

    本文实例分析了PHP数组操作.分享给大家供大家参考,具体如下: PHP的数组是很重要的一部分.操作示例如下: <?php function br() { echo '<br />===============================================<br />'; } $arr1 = array(); $arr1[] = 'x'; $arr1[] = 'a'; $arr1[] = 'e'; $arr1[] = 'c'; $arr1[] = 'h'; /

  • php获取数组中键值最大数组项的索引值 原创

    本文实例讲述了php获取数组中键值最大数组项的索引值的方法.分享给大家供大家参考.具体分析如下: 一.问题: 从给定数组中获取值最大的数组项的键值.用途如:获取班级得分最高的学生的姓名. 二.解决方法: <?php /* * Created on 2015-3-17 * Created by www.jb51.net */ $arr=array('tom'=>9,'jack'=>3,'kim'=>5,'hack'=>4); asort($arr); //print_r($ar

  • 求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:/

  • PHP获取数组最大值下标的方法

    本文实例讲述了PHP获取数组最大值下标的方法.分享给大家供大家参考.具体实现方法如下: <?php $hots = array('8213'=> 0,'8212'=> 100,'8172'=> 10008); $key = array_search(max($hots),$hots); echo $key; ?> 运行结果为:8172 希望本文所述对大家的php程序设计有所帮助.

  • PHP查找数值数组中不重复最大和最小的10个数的方法

    本文实例讲述了PHP查找数值数组中不重复最大和最小的10个数的方法.分享给大家供大家参考.具体如下: 1. php代码如下: //随机生成1万个元素的数组 for($i=0;$i<10000;$i++){ $ary[]=rand(1,100000); } $ary=array_unique($ary); //去重复数值 sort($ary);//顺序排序 $min_10=array_slice($ary,0, 10);//取出最小的10个数值 $max_10=array_slice($ary,-

随机推荐