题目描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:
1<=n<=2^10

题解：动态规划

代码

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
//         根据题意，数据范围n>1，所以不用考虑输入无效的情况
//         动态规划：使用临时变量
        int curSum = 0;
        int result = array[0];
        for(int i =0;i<array.size();i++){
            if(curSum <= 0)
                curSum = array[i];
            else
                curSum +=array[i];
            result = max(curSum, result);
        }
        return result;

    }
};

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
//         根据题意，数据范围n>1，所以不用考虑输入无效的情况
        //动态规划：使用数组
        //动态转移方程：dp[i] = max(dp[i-1]+array[i],array[i])
        vector<int> dp(array.size(),0);
        int result = array[0];
        dp[0] = array[0];
        for(int i =0;i<array.size();i++){
            dp[i] = max(dp[i-1]+array[i],array[i]);
            result = max(result,dp[i]);
        }
        return result;
    }
};

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
//         根据题意，数据范围n>1，所以不用考虑输入无效的情况
        int result = array[0];
        int temp = result;
        for(int i =1;i<array.size();i++){
            temp = max(array[i],temp+array[i]);
            result = max(temp,result);
        }
        return result;
    }
};