百度文库PHP面试题：给定一个整数数组，找出具有最大和的连续子数组，并返回最大和。

原始面试题目的要求如下：

给定一个整数数组，找出具有最大和的连续子数组，并返回最大和。
$nums = [-2,1 ,-3,4,-1,2,1,-5,4];
打印出最大和的连续子数组。

这道题看起来挺简单的。但是，我好久没写算法题了...写了10多分钟，没写完。我真的是变菜了😅。

上机实际写的时候，变量名起的太容易混淆了。例如：$num和$nums。我把变量名写错了好几次，导致查了半天的BUG。最后说了一下思路，面试官反馈思路正确。总之，面试估计是寄了。

题目的整体思路就是两个for循环，遍历整个数组。然后，计算当前循环数组值的相加之和。如果遇到最大的值，就记录下起始和结束的数组下标。最后打印即可。

下面是面试结束后重新写的代码，大约花费了20分钟左右，整体用时还是偏慢。看来面试还得多练算法题呀。

PHP版本解题代码如下：

function index(){
    $nums = [-2,1 ,-3,4,-1,2,1,-5,4];

    $count = count($nums);
    $arr = [];
    $max_key = 0;
    $max_value = -999999;

    for ($i = 0; $i < $count; $i++){
        $min = $i;
        $max = 0;
        $old = 0;
        for ($j = $i; $j < $count; $j++){
            $new = $old + $nums[$j];
            if($new > $old){
                $max = $j;
                $old = $new;

                $arr[$i]['min'] = $min;
                $arr[$i]['max'] = $max;
                $arr[$i]['all'] = $new;

                if($new >= $max_value){
                    $max_key = $i;
                    $max_value = $new;
                }
            }
        }
    }

    $return = [];

    for ($i = 0; $i < $count; $i++){
        if ($i >= $max_key && $i <= $arr[$max_key]['max']){
            $return[] = $nums[$i];
        }
    }

    print_r($return);
}

Golang版本：

package main

import (
    "fmt"
)

func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    maxInt := -99999
    start := 0
    end := 0
    count := len(nums)
    for i := 0; i < count; i++ {
        temp := -99999
        for j := i; j < count; j++ {
            temp = temp + nums[j]
            if temp > maxInt {
                maxInt = temp
                start = i
                end = j
            }
        }
    }

    sum := nums[start]
    for i := start + 1; i <= end; i++ {
        sum += nums[i]
    }

    fmt.Println(sum)
}

ChatGPT Golang版本：

package main

import "fmt"

func maxSubArray(nums []int) int {
    maxSum := nums[0]
    currentSum := nums[0]

    for i := 1; i < len(nums); i++ {
        // 判断当前元素加入子数组后，是否比当前元素更大
        currentSum = max(nums[i], currentSum+nums[i])
        // 判断当前子数组的和是否比当前最大和更大
        maxSum = max(maxSum, currentSum)
    }

    return maxSum
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
    maxSum := maxSubArray(nums)
    fmt.Println("最大和的连续子数组的和为:", maxSum)
}