题目
【学习计划 - 数据结构 - 第一天 - 数组】https://leetcode-cn.com/study-plan/data-structures/
https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
程序样例
1
2
3
| int maxSubArray(int* nums, int numsSize){
}
|
我的解答
关键代码
第一版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int maxSubArray(int* nums, int numsSize){
int maxnum=*(nums),sum=0;
for(int i=0;i<numsSize;i++){
sum += *(nums+i);
if(i-1>=0){
sum -= *(nums+i-1);
}
if(sum>maxnum){
maxnum = sum;
}
}
return maxnum;
}
|
成功版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int maxSubArray(int* nums, int numsSize){
int maxnum=*(nums),sum;
for(int i=1;i<=numsSize;i++){
sum =0;
for(int j=0;j<numsSize;j++){
sum += *(nums+j);
if(j-i>=0){
sum -= *(nums+j-i);
}
if(sum>maxnum){
maxnum = sum;
}
}
}
return maxnum;
}
|
思路：滑块。长度从1到最长。每向右滑一，减去最左边的那个元素。
第一版本为长度为1时的滑块，成功版本为长度从1到最长时的滑块。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <stdio.h>
int maxSubArray(int* nums, int numsSize){
int maxnum=*(nums),sum;
for(int i=1;i<=numsSize;i++){
sum =0;
for(int j=0;j<numsSize;j++){
sum += *(nums+j);
if(j-i>=0){
sum -= *(nums+j-i);
}
if(sum>maxnum){
maxnum = sum;
}
}
}
return maxnum;
}
main(){
int numsSize=5;
int nums[]={1,6,-2,-4,7};
int num = maxSubArray(nums,numsSize);
printf("--%d--\n",num);
}
|
复杂度分析
执行用时：908 ms, 在所有 C 提交中击败了5.15%的用户
内存消耗：6.2 MB, 在所有 C 提交中击败了79.89%的用户