package bytedance

fun main() {
    // 53. 最大子数组和
    // https://leetcode.cn/problems/maximum-subarray/
    println(maxSubArray1(intArrayOf(1)))
}

fun maxSubArray(nums: IntArray): Int {
    // 动态规划数组，dp[i] 表示以 nums[i] 结尾的子数组的和
    val dp = IntArray(nums.size)
    dp[0] = nums[0]
    var max = dp[0]
    for (i in 1 until nums.size) {
        if (dp[i-1] > 0) {
            dp[i] = dp[i-1] + nums[i]
        }else {
            dp[i] = nums[i]
        }
        if (max < dp[i]) {
            max = dp[i]
        }
    }
    return max
}

fun maxSubArray1(nums: IntArray): Int {
    // 优化版本，dp[i] 只和 dp[i-1] 有关，可以用一个变量替换 dp 数组，优化空间复杂度
    // 可以理解为：前面数组的和 prevSum 如果是正数的，对 nums[i] 来说是正贡献，可以累加到以 nums[i] 结尾的子数组的和上
    // 如果前面数组的和 prevSum 是负数的，对 nums[i] 来说是负贡献，那么以 nums[i] 结尾的子数组的和，就没必要加上 prevSum，
    // nums[i] 自己作为以  nums[i] 结尾的子数组的和就可以了
    var prevSum = nums[0]
    var max = prevSum
    for (i in 1 until nums.size) {
        if (prevSum > 0) {
            prevSum += nums[i]
        }else {
            prevSum = nums[i]
        }
        if (max < prevSum) {
            max = prevSum
        }
    }
    return max
}