欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

程序员文章站 2022-07-15 16:37:29
...

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

<?php
require ('function.php');

$arr = [];
$count = mt_rand(7, 12);
for ($i = 0; $i < $count; ++$i) {
	$arr[] = mt_rand(-5, 5);
}

dump($arr);

$lift = 0;
$right = 0;
$lift_right = 0;
$sum = 0;

if ($count % 2 == 0) { // 偶数

	$len = $count / 2;
	$count -= 1;
	
	for ($i = 0; $i < $len; ++$i) {
		$right_key = $count - $i;
		
		$lift += $arr[$i];
		$right += $arr[$right_key];
		
		if ($sum < $lift || $sum < $right) {
			$sum = $lift > $right ? $lift : $right;
		}
		
		if ($lift < 0)  $lift = 0;
		if ($right < 0)  $right = 0;
	}
	
	$lift_right = $lift + $right;
	if ($sum < $lift_right) $sum = $lift_right;
	
} else { // 奇数

	$count -= 1;
	$len = $count / 2;
	
	for ($i = 0; $i < $len; ++$i) {
		$right_key = $count - $i;
		
		$lift += $arr[$i];
		$right += $arr[$right_key];
		
		if ($sum < $lift || $sum < $right) {
			$sum = $lift > $right ? $lift : $right;
		}
		
		if ($lift < 0)  $lift = 0;
		if ($right < 0)  $right = 0;
	}
	
	$lift_right = $lift + $arr[$i] + $right;
	if ($sum < $lift_right) $sum = $lift_right;
	
}

dump($lift);
dump($right);
dump($sum);

执行结果:

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。