算法题->最大子数组和

ywlYWL 发表于 2021-12-25 22:12

本帖最后由 ywlYWL 于 2021-12-25 22:24 编辑

今天是学习算法的第二天

https://static.52pojie.cn/static/image/hrline/4.gif
题目:
//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
// 子数组是数组中的一个连续部分。
//
//
//// 示例 1：
//
//
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
//输出：6
//解释：连续子数组的和最大，为 6 。
//
//
// 示例 2：
//
//
//输入：nums =
//输出：1
//
//
// 示例 3：
//
//
//输入：nums =
//输出：23
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10⁵
// -10⁴ <= nums <= 10⁴

思路:定义一个前n项的和判断是否大于0大于0累加小于0 舍去继续按当前累加

public int maxSubArray(int[] nums) {
int ans=nums[0];
int max=0;
for (int num : nums) {
   if (max>0){
         max=max+num;
   }else {
         max=num;
   }
   ans=Math.max(max,ans);
}
return ans;

感触:
做题嘛,难免会没思路,把情景带入进去
模拟人脑解决过程
再用编程语言翻译过来就ok
加油! 小杨学编程! 明天会更好!
努力!希望看到贴的人,一切会变好!祝读者好运!

huyifan311 发表于 2021-12-25 22:32

这可真是高手半夜发出来的东西{:1_893:}小白表示一点不懂，{:1_918:}

luanshils 发表于 2021-12-25 23:21

绿颜色的字体挺晃眼的

藏起来的小尾巴,不让你看!

BBridgeW 发表于 2021-12-26 09:51

思路很棒。所以就是后一项为负的时候和一定会减小，最大就要从后面寻找。

平淡最真 发表于 2021-12-26 13:25

百度搜到的所有的输入数组都是同一个，全是抄抄抄，各种cv
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 :
输入 : [-2, 1, -3, 4, -1, 2, 1, -5, 4],
输出 : 6
解释 : 连续子数组的和最大，为 6。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int maxSubArray(int* nums, int numsSize) {
int sum = 0;
int max = nums;
for (int i = 0; i<numsSize; i++)
{
if (sum>0)
{
sum += nums;//只有sum大于0 加上一个数才有可能继续增大
}
if (sum <= 0)
{
sum = nums;//sum小于0 就让它等于第i位
}
if (sum>max)
{
max = sum;
}
}
return max;
}
int main()
{
int num[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int len = sizeof(num) / sizeof(int);
int a = maxSubArray(num, len);
printf("%d\n", a);
system("pause");
return 0;
}

mindream 发表于 2021-12-27 12:24

大佬Mt管理器破解版的有么？好像后面提示需要会员才能操作

帆爱世人 发表于 2021-12-27 16:17

mindream 发表于 2021-12-27 12:24
大佬Mt管理器破解版的有么？好像后面提示需要会员才能操作

同求,找了好久没找到破解版的mt

页: [1]

吾爱破解 - 52pojie.cn's Archiver

算法题->最大子数组和