PHP求最大子序列和的算法实现

代码如下:

<?php
//作者：遥远的期待
//QQ:15624575
//算法分析：1、必须是整数序列、2、如果整个序列不全是负数，最大子序列的第一项必须是正数，否则最大子序列后面的数加起来再加上第一项的负数，其和肯定不是最大的；3、如果整个序列都是负数，那么最大子序列的和是0；
//全负数序列很简单，不举例
$arr=array(4,-3,5,-2,-1,2,6,-2);
function getmaxsum($arr){
$thissum=0;
$maxsum=0;
$start=0;//记录子序列的起始下标
$end=0;//记录子序列的结束下标
for($i=0;$i<count($arr);$i++){
$thissum+=$arr[$i];//取得当前子序列的和
if($thissum>$maxsum){//如果当前子序列的和大于当前最大子序列的和
$maxsum=$thissum;//改变当前最大子序列的和
$end=$i;
}else if($thissum<0){//如果当前子序列的和小于0，则把下一个元素值假定为最大子序列的第一项,这里可以保证最大自序列的第一项一定是正数
$thissum=0;//前提这个序列不全是负数
$start=$i+1;
}
}
$parr=array($start,$end,$maxsum);
return $parr;
}
list($start,$end,$maxsum)=getmaxsum($arr);
echo '最大子序列是:';
for($i=$start;$i<=$end;$i++){
echo $arr[$i].' ';
}
echo '<br>';
echo '最大子序列的和是'.$maxsum;
?>

赞 (0)

相关推荐

  • PHP求最大子序列和的算法实现

    复制代码 代码如下: <?php //作者:遥远的期待 //QQ:15624575 //算法分析:1.必须是整数序列.2.如果整个序列不全是负数,最大子序列的第一项必须是正数,否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的:3.如果整个序列都是负数,那么最大子序列的和是0: //全负数序列很简单,不举例 $arr=array(4,-3,5,-2,-1,2,6,-2); function getmaxsum($arr){ $thissum=0; $maxsum=0; $star

  • Java实现求数组最长子序列算法示例

    本文实例讲述了Java实现求数组最长子序列算法.分享给大家供大家参考,具体如下: 问题:给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱) 例如:给定一个长度为8的数组A{1,3,5,2,4,6,7,8},则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6. 思路1:第一眼看到题目,很多人肯定第一时间想到的是LCS.先给数组排个序形成新数组,然后再把新数组和原数组拿来求LCS,即可得到答案.这种解法很多人能想得到,所以就不再赘述. 思路2:按照思路1的

  • Python编程实现数学运算求一元二次方程的实根算法示例

    Python编程实现数学运算求一元二次方程的实根算法示例

    本文实例讲述了Python编程实现数学运算求一元二次方程的实根算法.分享给大家供大家参考,具体如下: 问题: 请定义一个函数quadratic(a, b, c),接收3个参数,返回一元二次方程:ax² + bx + c = 0的两个解. 实现代码: #!/usr/bin/env python # -*- coding: utf-8 -*- import math def quadratic(a,b,c): if a == 0: raise TypeError('a不能为0') if not is

  • Java求最小生成树的两种算法详解

    Java求最小生成树的两种算法详解

    目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结 介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的

  • 一种求正整数幂的高效算法详解

    核心思想是当n为偶数时,a^n = a^n/2 × a^n/2当n为奇数时,a^n = a^(n-1)/2 × a^(n-1)/2  × a代码如下: 复制代码 代码如下: public class Power { public static void main(String[] args) {  System.out.println(power(5.5,5)); } private static double power(double base, int exponent) {  if (ex

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

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

  • java实现字符串匹配求两个字符串的最大公共子串

    java实现字符串匹配求两个字符串的最大公共子串

    本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • 基于C++的拼多多算法在线笔试题示例

    本文实例讲述了基于C++的拼多多算法在线笔试题.分享给大家供大家参考,具体如下: 最近在狼厂实习中,很久没做题了.秋招第一发, 拼多多...  四个简单题,看到有些人竟然觉得难? 我来降一发自己的RP,这题目觉得难的,如果你拿到比我好的Offer,我是不服气的.. 四个题...其实我也就写了40分钟吧..不过最后也没有满分, 390/400, 第三题不知道为嘛一直有10分过不了.. 更一下, 刚刚好像发现第三题...这个>号, 我写的是>= ....? 可是我看题目好像是 >= 呀...

  • 数据结构课程设计-用栈实现表达式求值的方法详解

    数据结构课程设计-用栈实现表达式求值的方法详解

    1.需求分析设计一个程序,演示用算符优先法对算术表达式求值的过程.利用算符优先关系,实现对算术四则混合运算表达式的求值.(1)输入的形式:表达式,例如2*(3+4)     包含的运算符只能有'+' .'-' .'*' .'/' .'('. ')':(2)输出的形式:运算结果,例如2*(3+4)=14:(3)程序所能达到的功能:对表达式求值并输出 2.系统设计1.栈的抽象数据类型定义:ADT Stack{数据对象:D={ai|ai∈ElemSet,i=1,2,-,n,n≥0}数据关系:R1={<

随机推荐