【Leetcode】最大子数组和
2022/4/12 23:42:54
本文主要是介绍【Leetcode】最大子数组和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
采用分治算法,
数组区间[left, right], mid = (right + left) / 2
最大子数组存在于可能的三种情况:
[left, mid], [mid + 1, right], 横跨前两个
而第三种情况可以拆成[lb, mid] 和 [mid + 1, ub]的并集
class Solution { public: int maxSubArray(vector<int>& nums) { if (nums.size() == 1) return nums[0]; if (nums.size() == 2) return max(nums[0], nums[1], nums[0] + nums[1]); int left = 0, right = nums.size() - 1, mid = left + (right - left) / 2; int left_max = nums[mid], right_max = 0, cur_left = 0, cur_right = 0; vector<int>left_nums, right_nums; for (int i = mid; i >= 0; --i) { cur_left += nums[i]; if (cur_left > left_max) left_max = cur_left; left_nums.push_back(nums[i]); } if (mid + 1 <= right) right_max = nums[mid + 1]; for (int i = mid + 1; i <= right; ++i) { cur_right += nums[i]; if (cur_right > right_max) right_max = cur_right; right_nums.push_back(nums[i]); } return max(maxSubArray(left_nums), maxSubArray(right_nums), left_max + right_max); } int max(int a, int b, int c) { int m = a; if (m < b) m = b; if (m < c) m = c; return m; } };
这篇关于【Leetcode】最大子数组和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享