子序列求最大和

时间:2022-06-15 11:04:25

给一个数组,求子序列的最大和
开始是这样做的。

    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int m = nums[0];
        for (int i = 0; i < len; ++i) {
            dp[i][i] = nums[i];
            for (int j = i+1; j < len; ++j) {
                dp[i][j] = dp[i][j-1] + nums[j];
            }
        }
        for (int k = 0; k < len; ++k) {
            for (int i = k; i < len; ++i) {
                m = max(m, dp[k][i]);
            }
        }
        return m;
    }

然后TLE了。
想着想着拥有最大和的子序列一定以正数开头,那么代码就变成了这样。

    int maxSubArray(vector<int>& nums) {
            int len = nums.size();
            int m = -1;
 int ans = -2147483648;
            for (int i = 0; i < len; ++i) {
                if(nums[i] < 0) continue;
                m = 0;
                for (int j = i; j < len; ++j) {
                    m += nums[j];
                    if(m > ans)
                    {
                        ans = m;
                    }
                }
            }
        if(m == -1)
        {
            for (int i = 0; i < len; ++i) {
                if(nums[i] > ans)
                {
                    ans = nums[i];
                }
            }
        }
            return ans;
    }

没问题了,但是看到了一个答案居然是9ms!而我的是103ms!
差在哪里呢?然后就把代码再次改成了这样。

    int maxSubArray(vector<int>& nums) {
            int len = nums.size();
            int max = nums[0];
            int ans[len];
        ans[0] = nums[0];
            for (int i = 1; i < len; ++i) {
                ans[i] = nums[i] + (ans[i-1]>0 ? ans[i-1] : 0);
                max = ans[i]>max ? ans[i] :max;
            }
            return max;
    }

如此简单暴力的代码,棒透了,通过一个数组减少循环的开销,而且?:表达式比if效率高。