给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
程序员文章站
2022-07-15 16:37:29
...
<?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);
执行结果:
上一篇: leetcode 第907题 子数组的最小值之和 python解法
下一篇: 连续子数组的最大和