package daily.easy

fun main() {
    // 1800. 最大升序子数组和
    // https://leetcode.cn/problems/maximum-ascending-subarray-sum/
    println(maxAscendingSum1(intArrayOf(10,20,30,5,10,50)))
}
fun maxAscendingSum(nums: IntArray): Int {
    if (nums.size == 1) {
        return nums[0]
    }

    var max = 0
    var tmpMax = nums[0]
    for (i in 1 until nums.size) {
        if (nums[i] > nums[i-1]) {
            // 升序的
            tmpMax += nums[i]
        }else {
            if (tmpMax > max) {
                max = tmpMax
            }
            // 更新 tmpMax
            tmpMax = nums[i]
        }
    }
    if (tmpMax > max) {
        // 和最大的升序自数组在最后
        max = tmpMax
    }
    return max
}

fun maxAscendingSum1(nums: IntArray): Int {
    /**
     * 动态规划
     * 1、状态定义：dp[i] 表示以 nums[i] 结尾的升序子数组的和
     * 2、递推公式：分两种情况
     *   2.1 升序的，nums[i] >= nums[i-1]：dp[i] = dp[i-1] + nums[i]
     *   2.2 降序的，nums[i] < nums[i-1]：dp[i] = nums[i]
     * 3、初始值：dp[0] = nums[0]
     */
    val dp = IntArray(nums.size)
    dp[0] = nums[0]
    var max = dp[0]
    for (i in 1 until nums.size) {
        dp[i] = if (nums[i] > nums[i-1]) {
            dp[i-1] + nums[i]
        }else {
            nums[i]
        }
        if (max < dp[i]) {
            max = dp[i]
        }
    }
    return max
}