leetcode【53-最大子序和】思考、优化、改进

一时失言乱红尘 2023-01-10 03:56 20阅读 0赞

# leetcode【53-最大子序和】思考、优化、改进 #

声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

class Solution { 
    public:
        int maxSubArray(vector<int>& nums) { 
            vector<int> dp(nums.size());
            dp.assign(nums.begin(),nums.end());
            for(int i =1;i<nums.size();i++)
                dp[i] = max(dp[i-1]+nums[i],nums[i]);
            int res =dp[0];
            for(int i =1;i<nums.size();i++)
            if(dp[i]>res)
            res = dp[i];
            return res;
        }
    };
    执行用时：8 ms, 在所有 C++ 提交中击败了96.44%的用户
    内存消耗：13 MB, 在所有 C++ 提交中击败了93.74%的用户

又是一道较为经典简单的dp问题,dp\[i\]表示的是以i为结尾的最大子序和，这样设置的话状态转移方程就变成了  
max(dp\[i-1\]+nums\[i\],nums\[i\])，再次遍历一遍即可得到结果。 虽 然 时 间 空 间 的 结 果 都 不 错 ， 但 我 在 想 ， 这 个 题 是 否 能 用 状 态 压 缩 进 一 步 减 少 空 间 时 间 复 杂 度 呢 ？ \\color\{\#FF0000\}\{虽然时间空间的结果都不错，但我在想，这个题是否能用状态压缩进一步减少空间时间复杂度呢？\} 虽然时间空间的结果都不错，但我在想，这个题是否能用状态压缩进一步减少空间时间复杂度呢？  
 毕 竟 d p \[ i \] 的 计 算 仅 仅 与 n u m s \[ i \] 和 d p 的 前 一 项 d p \[ i − 1 \] 相 关 . \\color\{\#FF0000\}\{毕竟dp\[i\]的计算仅仅与nums\[i\]和dp的前一项dp\[i-1\]相关.\} 毕竟dp\[i\]的计算仅仅与nums\[i\]和dp的前一项dp\[i−1\]相关.  
 仔 细 分 析 一 下 ， 写 出 如 下 代 码 。 ” \\color\{\#FF0000\}\{仔细分析一下，写出如下代码。”\} 仔细分析一下，写出如下代码。”

int maxSubArray(vector<int>& nums) { 
            vector<int> dp(nums.size());
            int pre = nums[0],maxn = nums[0];
            for(int i =1;i<nums.size();i++)
               {  pre = max(nums[i],pre+nums[i]);
                maxn = max(maxn,pre);
               }
    
            return maxn;
        }
    执行用时：16 ms, 在所有 C++ 提交中击败了54.13%的用户
    内存消耗：13 MB, 在所有 C++ 提交中击败了93.89%的用户

如 此 巧 妙 的 状 态 压 缩 方 法 。 。 竟 然 只 在 内 存 消 耗 上 提 高 了 不 到 0.1 个 百 分 点 ， 然 而 却 让 时 间 暴 增 ! ! ! \\color\{\#FF0000\}\{如此巧妙的状态压缩方法。。竟然只在内存消耗上提高了不到0.1个百分点，然而却让时间暴增!!!\} 如此巧妙的状态压缩方法。。竟然只在内存消耗上提高了不到0.1个百分点，然而却让时间暴增!!!  
仔细思考一下原因，是因为首先样本长度并不高，所以节省的空间并不大，其次对于长度为n的nums数组，采用状态压缩的方法每次循环中一次加操作(pre+nums\[i\])调用两次max函数（也就是一个if比较）。  
而方法1使用一次max函数，一次加操作，一个遍历（也相当于比较）为什么时间差距这么大呢？

#  挖 坑 . . . 暂 时 没 想 明 白 ， 或 者 是 哪 里 想 错 了 ， 欢 迎 大 家 讨 论 ， 指 正 \\color\{\#FF0000\}\{挖坑...暂时没想明白，或者是哪里想错了，欢迎大家讨论，指正\} 挖坑...暂时没想明白，或者是哪里想错了，欢迎大家讨论，指正 #

补坑1  
由于我是实在想不明白，我又原封不动运行了一次，结果如下

执行用时：4 ms, 在所有 C++ 提交中击败了99.44%
    的用户内存消耗：13 MB, 在所有 C++ 提交中击败了93.60%的用户

惊了，好起来了。应该是  
判题服务器有波动造成的，现在服务器都是云服务器，性能小幅波动正常的。  
以后还是要多执行几次，并且不要的一味看这个执行时间，这次真的是学到了。