【LeetCode】053. Maximum Subarray

题目：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

题解：

　　遍历所有组合，更新最大和。

Solution 1 (TLE)

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int n = nums.size(), result = nums[];

        for(int i=; i<n; ++i) {

            int tmp = nums[i];

            result = max(tmp,result);

            for(int j=i+; j<n; ++j) {

                 tmp += nums[j];

                 result = max(tmp,result);

            }

        }

        return result;

    }

};

　　可以看做动态规划的简略版，见Solution 5

Solution 2 ()

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int n = nums.size(), result = nums[], tmp = ;

        for(int i=; i<n; ++i) {

              tmp = max(tmp + nums[i], nums[i]);

              result = max(result, tmp);

        }

        return result;

    }

};

　　贪心算法：The idea is to find the largest difference between the sums when you summing up the array from left to right. The largest difference corresponds to the sub-array with largest sum

Solution 3 ()

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int sum = , minsum = , result = nums[], n = nums.size();

        for(int i = ; i < n; i++) {

            sum += nums[i];

            if(sum - minsum > res) result = sum - minsum;

            if(sum < minsum) minsum = sum;

        }

        return result;

    }

};

　　分治法：

Solution 4 ()

　　DP算法：维护一个一维数组。

Solution 5 ()

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int n = nums.size();

        vector<int> dp(n,);//dp[i] means the maximum subarray ending with nums[i];

        dp[] = nums[];

        int max = dp[];

        for(int i = ; i < n; i++){

            dp[i] = nums[i] + (dp[i - ] >  ? dp[i - ] : );

            max = Math.max(max, dp[i]);

        }

        return max;

    }

};

巴特西

【LeetCode】053. Maximum Subarray

最新文章

热门文章