Home >Backend Development >PHP Problem >Given an array, find the sum of the largest consecutive subsequences in the array

Given an array, find the sum of the largest consecutive subsequences in the array

王林
王林Original
2019-10-29 09:19:313299browse

Given an array, find the sum of the largest consecutive subsequences in the array

The time complexity is O(n)

You only need to go through the array once, but you need to deeply understand the essential characteristics of this array. That is, the method of dynamic programming.

First set two variables, thisSum and maxSum. Among them, thisSum represents the sum of elements reaching the current position; maxSum represents the maximum sum of consecutive subsequences reaching the current position.

Note: If thisSum is negative, set it to 0 directly; if thisSum is greater than maxSum, set maxSum to the value of thisSum.

public static int maxSubArray(int[] nums)
    {
        int length = nums.length;
        if(length <= 0)
            return 0;
        int CurSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < length; i++)
        {
            if(CurSum <= 0)     //当当前的和小于等于0,那么就给其置为当前元素的值
                CurSum = nums[i];
            else
                CurSum += nums[i];
            if(CurSum > max)
                max = CurSum;
        }
        return max;
    }

Recommended tutorial: PHP tutorial

The above is the detailed content of Given an array, find the sum of the largest consecutive subsequences in the array. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn