思路1
1.暴力解法,两重循环,从某一个下标开始,计算连续的和,求最大
代码
class Solution { public: int maxSubArray(vector<int> &nums) { //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值 int max = INT_MIN; int numsSize = int(nums.size()); for (int i = 0; i < numsSize; i++) { int sum = 0; for (int j = i; j < numsSize; j++) { sum += nums[j]; if (sum > max) { max = sum; } } } return max; } };
思路2 动态规划
class Solution { public: int maxSubArray(vector<int>& nums) { int pre = 0,Max_val = nums[0]; for(const auto &x:nums) //需要改变迭代对象 加& { pre = max(pre+x,x); //选择每一步加入的值进行比较,去较大的值作为加入当前的子序列 Max_val = max(Max_val,pre); } return Max_val; } };
思路3
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ len_num = len(nums) for i in range(1,len_num): nums[i] = max(nums[i],nums[i]+nums[i-1]) return max(nums)