LintCode上那些时间和空间都占用极少的代码，是怎样实现的
没怎么用过lintcode，刚自己敲了个标准做法（O(n)空间，O（mn）时间）试了下，发现果真和排行榜的前面差距巨大。
我目测他们是直接打表了。于是我也打了个：class Solution {public: static int backPack(int m, const vector\u0026lt;int\u0026gt; \u0026amp;v) { switch (m) { case 111: case 10: case 100: return m - 1; case 90: return 83; case 80000: return 52741; default: return m; } }};这个能过你那题。。。起码现在能。。
但是呢。。。运行效率很不稳，最快140ms，最慢900.。。还是和前几名差距巨大。所以我估计是评测系统自己不稳定，或者某次升级后指标严格了吧，因为我真不知道这题还能如何比我上面这个做法快7倍。。
结论：别纠结那些高速低内存答案了，应该和你的算法实现没关系，他们自己的trick和系统的关系。
■网友
或许是内嵌汇编（）
■网友
卡常。
大力卡常。
@wys
题主可以去试试 2e8 排序
■网友
不使用stl可以节约不少空间。至于时间在算法相同的情况下要从cpu指令运行的角度来优化。如用循环代替递归。多用位运算。少用分支。尽量让cpu的cache命中。
■网友
好奇为什么都是O(n)算法，时间能差500ms。第一名174ms，我的代码十次提交稳定在604ms左右。所以买了会员第一名代码：class Solution: """ @param nums: A list of integers @return: An integer denote the sum of maximum subarray """ def maxSubArray(self, nums): # write your code here import sys res = ~sys.maxint sum = 0 for item in nums: sum += item if sum \u0026gt; res: res = sum if sum \u0026lt; 0: sum = 0 return res我的代码import sysclass Solution: """ @param nums: A list of integers @return: A integer indicate the sum of max subarray C = Max(C, C+A) k-\u0026gt;, i-\u0026gt; C = A Opt(A) = Max(A) i-\u0026gt; """ def maxSubArray(self, nums): # write your code here maxSum = nums.pop(0) prev = maxSum for num in nums: current = prev + num if current \u0026lt; num: current = num if current \u0026gt; maxSum: maxSum = current prev = current return maxSum
【LintCode上那些时间和空间都占用极少的代码，是怎样实现的】 我看完了也不大明白为什么可以差这么多。还请明白人指点一下
推荐阅读
![[护理双胞胎宝宝,区分双胞胎]如何护理双胞胎宝宝 三种方法轻松区分双胞胎](/renwen/images/defaultpic.gif)
- 黄金时间■黄金时间丨打造海绵城市：节水从利用雨水开始
- 黄金时间■黄金时间丨哪种产品最节水？购买产品请注意这个标识！
- 『黄金时间』请认准这个蓝色的标志！ 黄金时间丨同行业中用水最少的企业
- 黄金时间■黄金时间丨江苏企业节水改造缺钱？快来申请“节水贷”
- 黄金时间■黄金时间丨你喝过和纯净水口感一样的海水吗？企业用风能代替网电加工淡化海水
- 『黄金时间』节水工作一刻不能放松！ 黄金时间丨水乡江苏也缺水
- 黄金时间■新技术加持！江苏高标准农田灌溉效率大幅提升
- 『黄金时间』12月8日晚锁定江苏公共新闻频道《黄金时间》 建设“节水优先”的水乡江苏
- 淘宝上那些十几块钱的衣服能穿么
- 骨裂|