1、问题描述
在数组中，有正数，负数，0，求其最大子数组和？
算法思想：穷举的解法，找出所有的子数组和，利用3层for循环；
去冗余--->贪心算法，将小于0的子数组直接淘汰，因为之前已经保存过最大子数组值了；
2、暴力破解
计算
安全
数据库
网络和加速
企业服务
#include<stdio.h>
//求最大子数组和，暴力破解法，时间复杂度：O(n^3)
int maxSubArray(int *a, int n);
int maxSubArray(int *a, int n){
int i;
int j;
int k;
int ans = -100000000;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){
int sum = 0;
for(k = i; k <= j; k++){
sum += a[k];
}
if(sum > ans){
ans = sum;
}
}
}
return ans;
}
void main(void){
int a[] = {1, -2, -3, 3, 5, 6, -1};
int count = sizeof(a)/sizeof(int);
int maxNumber;
maxNumber = maxSubArray(a, count);
printf("%d\n", maxNumber);
}结果截图
3、贪心算法
#include<stdio.h>
//最大子数字和：贪心算法,时间复杂度为：O(n)
int maxSubArray(int *a, int n);
int maxSubArray(int *a, int n){
int i;
int ans = -10000000;
int sum = 0;
for(i = 0; i < n; i++){
sum += a[i];
if(sum > ans){
ans = sum; //保存先前的最大值
}
if(sum < 0){
sum = 0; //将一部分和<0的直接删去
}
}
return ans;
}
void main(void){
int a[] = {-1, -2, 3, 6, -6, 3, 3, 2, -3};
int count = sizeof(a)/sizeof(int);
int maxNumber;
maxNumber = maxSubArray(a, count);
printf("%d\n", maxNumber);
}结果截图
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
