Algorithm -- continuous sequence (kotlin)

subject

Given an array of integers , Find the sequence with the largest sum , And return the sum .

Example ：

Input ： [-2,1,-3,4,-1,2,1,-5,4]
Output ： 6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6.
Advanced ：

If you have implemented complexity as O(n) Solution method , Try to use a more sophisticated divide and conquer method to solve .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/contiguous-sequence-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solutions

resolvent

    fun maxSubArray(nums: IntArray): Int {
    
        val dp = Array(nums.size) {
     0 }
        var max = if (nums.isNotEmpty()) nums[0] else 0
        nums.forEachIndexed {
     index, i ->
            if (index >= 1) {
    
                dp[index] = i.coerceAtLeast(dp[index - 1] + i)
            } else {
    
                dp[index] = i
            }
            max = max.coerceAtLeast(dp[index])
        }
        return max
    }

summary

1. Don't look at simplicity I did it three times before I passed
2. Not clear thinking