LeetCode--用PHP实现最大子序和（动态规划和分治）

我就是我 2023-07-10 14:20 1阅读 0赞

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

**示例:**

输入: [-2,1,-3,4,-1,2,1,-5,4],
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

**进阶:**

如果你已经实现复杂度为 O(*n*) 的解法，尝试使用更为精妙的分治法求解。

方法一：

用了三层循环，因为要找到这个子序列，肯定是需要起点和终点的，所以第一层循环确定起点，第二层循环确定终点，第三层循环在起点和终点之间遍历。时间复杂度：O(N^3)

方法二：

用了一层循环, 遍历寻找子序列的同时，对其进行求和，然后和最大值比较，求的最大值，这种情况的一个隐含条件是数组中必须至少有一个非负数，所以需要对全为负数的情况单独处理，这样就可以得到正确的结果。时间复杂度：O(n)。

class Solution {
    
        /**
         * @param Integer[] $nums
         * @return Integer
         */
        function maxSubArray($nums) {
            $len = count($nums);
    
            $sum = 0;
            $flag = false;
            $min = PHP_INT_MIN;
            $max = 0;
            for($i=0; $i<$len; $i++){
                if($nums[$i]>0){
                    $flag = true;
                }else{
                    if($nums[$i]>$min){
                        $min = $nums[$i];
                    }
                }
    
    
                $sum += $nums[$i];
                if($sum>$max){
                    $max = $sum;
                }else if($sum<0){
                    $sum = 0;
                }
            }
    
            return $flag ? $max : $min;
        }
    }

方法三：

分治法：把大问题分为小问题，是“分”，然后对小问题进行处理，是“治”。这就是分治法的核心思想。

class Solution {
    
        function maxSum($nums, $start, $end){
            if($start === $end){
                return $nums[$start];
            }
    
            $mid = intval(($start+$end)/2);
            $lsum = $this->maxSum($nums, $start, $mid);//左边的
            $rsum = $this->maxSum($nums, $mid+1, $end);//右边的
            $t = 0;//计算中间部分的
            $t1 = PHP_INT_MIN;
            $t2 = PHP_INT_MIN;
            for($i=$mid; $i>=$start; $i--){
                $t += $nums[$i];
                if($t > $t1){
                    $t1 = $t;
                }
            }
    
            $t = 0;
            for($i=$mid+1; $i<=$end; $i++){
                $t += $nums[$i];
                if($t > $t2){
                    $t2 = $t;
                }
            }
    
            $msum = $t1 + $t2;
    
            return max($lsum, max($msum, $rsum));
        }
    
        function maxSubArray($nums){
            $len = count($nums);
    
            return $this->maxSum($nums, 0, $len-1);
    
        }
    }