# 最大子序列和（leetcode）

1.暴力求解（超时）

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int sum;
for(int i = 0;i < nums.size();i++){
for(int j = i;j < nums.size();j++){
sum = 0;//计算nums[i]到nums[j]
for(int k = i;k <= j;k++){
sum = sum + nums[k];
if(maxSum < sum) maxSum = sum;
}
}
}
return maxSum;
}
};```

2.暴力求解进化版：重复计算nums[i]到nums[j-1]的值

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int sum;
for(int i = 0;i < nums.size();i++){
sum = 0;
for(int j = i;j < nums.size();j++){
sum = sum + nums[j];
if(maxSum < sum) maxSum = sum;
}
}
return maxSum;
}
};```

3.贪心算法

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int arrSum = nums[0];
for(int i = 1;i < nums.size();i++){
arrSum = max(nums[i],arrSum + nums[i]);
maxSum = max(maxSum, arrSum);
}
return maxSum;
}
};```

4.分治法

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
int right = nums.size()-1;
int left = 0;
int result = maxSubArrayHelp(nums, left, right);
return result;
}
int maxSubArrayHelp(vector<int>& nums,int left,int right){
//递归中止条件
if(left == right) return nums[left];

//递归
int mid = (left + right)/2;
int leftsum = maxSubArrayHelp(nums, left, mid);
int rightsum = maxSubArrayHelp(nums, mid+1, right);
int midsum = maxSubArrayMid(nums, left, right, mid);

//判断三者中的最大值
int result = max(leftsum, rightsum);
int z = max(result, midsum);

return z;
}

int maxSubArrayMid(vector<int>& nums,int left, int right,int mid){
int leftSum = INT_MIN;
int sum = 0;

//从mid开始向左的序列的最大值
for(int i = mid;i >= left;i--){
sum = sum + nums[i];
leftSum = max(sum, leftSum);
}
int rightSum = INT_MIN;
sum = 0;
//从mid向右的最大值
for(int j = mid+1;j <= right;j++){
sum = sum + nums[j];
rightSum = max(sum, rightSum);
}

return rightSum + leftSum;
}
};```

0 条评论

• ### 杨辉三角 II（leetcode.119）

Cnk​=n!/(k!(n−k)!)=(n∗(n−1)∗(n−2)∗...(n−k+1))/k!

• ### 寒假学习计划

今年考研感觉不太好，借助寒假系统的复习一遍java web和大学其他知识（还有高数/(ㄒoㄒ)/~~）

• ### LeetCode 494. 目标和（DFS+DP）

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符...

• ### 【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

• ### Leetcode 1365. 有多少小于当前数字的数字（C语言）

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

• ### LeetCode 666. 路径和 IV（树的遍历）

给定一个包含三位整数的升序数组，表示一棵深度小于 5 的二叉树， 请你返回从根到所有叶子结点的路径之和。

• ### 小白刷力扣之两数之和

作为一个半路出家的算法小白，最近尝试着刷一下力扣，来扩展些思维，毕竟总是写一些复杂度非常高的代码也不是那么回事。

• ### Leetcode 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find ...