leetcode53：最大子数组和

题目链接

leetcode

题目描述

一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]";
}

void printArray(const vector<int>& nums, int l, int r) {
    cout << "[";
    for (int i = l; i < r; i++) {
        cout << nums[i] << ",";
    }
    cout << "]";
}

/*
    状态表示：
        f[i] 表示以第 i 个数字为结尾的连续子数组的总和，取 max。
    状态计算：
        f[i] = max(f[i-1] + nums[i], nums[i])
        两种决策：
            一种是将第 i 个数字与前边的数字拼接起来；
            另一种是第 i 个数字单独作为一个新的子数组的开始。
    答案：res = max(f[k]), 0 <= k < n
    
    时间复杂度：O(n)
        其中 n 是数组的长度。
        状态数为 O(n)，转移时间为 O(1)，所以总的时间复杂度为 O(n)。
    空间复杂度：O(n)
*/
class Solution_0 {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1);
        f[0] = 0;
        int res = INT_MIN;
        for (int i = 1; i <= n; i++) {
            f[i] = max(f[i-1] + nums[i-1], nums[i-1]);
            res = max(res, f[i]);
        }
        return res;
    }
};

/*
    思路同上，优化空间

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // max_sum 表示遍历到目前为止的最大子数组和
        // cur_sum 表示当前元素之前的最大子数组和
        int max_sum = INT_MIN;
        int cur_sum = 0;
        // int start = 0, end = 0;
        // int temp_start = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            if (max_sum < cur_sum) {
                max_sum = cur_sum;
                // start = temp_start;
                // end = i;
            }
            if (cur_sum < 0) {
                cur_sum = 0;
                // temp_start = i+1;
            }
        }

        // 返回最大子数组
        // printArray(nums, start, end + 1);
        return max_sum;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> nums = { 
        {-2,1,-3,4,-1,2,1,-5,4},
        {1},
        {5,4,-1,7,8}
    };

    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        cout << endl;
        int result = solution.maxSubArray(num);
        cout << "Output: " << result << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
    动态规划，在一次遍历中找到最大子数组的和。

    维护两个变量来动态更新最大子数组和：
        currentSum：当前子数组的和。
        maxSum：现在找到的最大子数组和。
    在遍历数组的过程中，对于每个元素 nums[i]：
        若当前和为负数，则将当前和重置为当前元素；
        否则，将当前和加上当前元素。
    同时，每次更新 currentSum 后，都检查是否需要更新 maxSum。

   时间复杂度：O(n)
       其中 n 是数组的长度，遍历数组的每个元素，所以时间复杂度为 O(n)。
   空间复杂度：O(1)
       只使用了固定的几个变量，所以空间复杂度为 O(1)。
*/
func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // 初始化：全局最大和、当前最大和
    maxSum, curSum := nums[0], nums[0]
    for i := 1; i < len(nums); i ++ {
        curSum = max(curSum + nums[i], nums[i])
        maxSum = max(maxSum, curSum)
    }
    return maxSum
}

/*
    将数组分成两半，分别计算左半部分和右半部分的最大子数组和，
    然后，结合这两部分来找到跨越中点的最大子数组和。

    时间复杂度：O(n)
        其中 n 是数组的长度。
        递归的过程看作是一颗二叉树的先序遍历。
    空间复杂度：O(logn)
        递归使用的栈空间为 O(logn)。
*/
func maxSubArray_1(nums []int) int {
    res := int(-1e9) // 使用一个足够小的数作为初始值
    for _, x := range nums {
        res = max(res, x)
    }
    if res < 0 {
        return res
    }

    t := build(nums, 0, len(nums) - 1)
    return t.ms
}

type Node struct {
    ls  int // 最大前缀和
    rs  int // 最大后缀和
    ms  int // 最大子段和
    sum int // 总和（当前子数组的）
}

func build(nums []int, l, r int) Node {
    if l == r {
        v := max(nums[l], 0)
        return Node{v, v, v, nums[l]}
    }

    mid := (l + r) / 2
    L := build(nums, l, mid)
    R := build(nums, mid + 1, r)
    res := Node{}

    res.ls = max(L.ls, L.sum + R.ls)
    res.rs = max(R.rs, R.sum + L.rs)
    res.ms = max(max(L.ms, R.ms), L.rs + R.ls)
    res.sum = L.sum + R.sum
    return res
}

func main() {
    // 测试用例
	testCases := []struct {
		nums     []int
		expected int
	}{
		{[]int{-2,1,-3,4,-1,2,1,-5,4}, 6},
		{[]int{1}, 1},
		{[]int{5,4,-1,7,8}, 23},
	}

    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		result := maxSubArray(tc.nums)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}