/*
* @lc app=leetcode.cn id=53 lang=c
*
* [53] 最大子序和
*
* https://leetcode-cn.com/problems/maximum-subarray/description/
*
* algorithms
* Easy (42.92%)
* Total Accepted: 39.9K
* Total Submissions: 93K
* Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
*
* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
*
* 示例:
*
* 输入: [-2,1,-3,4,-1,2,1,-5,4],
* 输出: 6
* 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
* [-2,1]
* [1,2]
*
* 进阶:
*
* 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
*
*/
int maxSubArray(int* nums, int numsSize) {
if(numsSize==){
return nums[];
}
int i=,j=,max=-,sum;
for(i=;i<numsSize;i++){
sum=nums[i];
j=i+;
while(j<numsSize){
sum+=nums[j];
if(sum>max){
max=sum;
}
j++;
}
}
for(i=;i<numsSize;i++){
if(nums[i]>max){
max = nums[i];
}
}
return max;
}
这是自己的傻屌代码。。。运行效率及其差。
核心思想就是，先进行两层循环，然后逐一的比较大小赋予max新的值。
然后再进行一轮循环，找出是否有单个值就大于max的值，有的话赋予max新的值。
所以时间复杂度达到了O（n²+n)
这道题真正的解法应该是用动态规划的方法：
设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i]
= max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小
/*
* @lc app=leetcode.cn id=53 lang=c
*
* [53] 最大子序和
*
* https://leetcode-cn.com/problems/maximum-subarray/description/
*
* algorithms
* Easy (42.92%)
* Total Accepted: 39.9K
* Total Submissions: 93K
* Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
*
* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
*
* 示例:
*
* 输入: [-2,1,-3,4,-1,2,1,-5,4],
* 输出: 6
* 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
* [-2,1]
* [1,2]
*
* 进阶:
*
* 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
*
*/
int maxSubArray(int* nums, int numsSize) {
int sum=,max=nums[];
for(int i=;i<numsSize;i++)
{
if(sum>)
sum+=nums[i];
else
sum=nums[i];
if(sum>max)
max=sum;
}
return max;
}
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
pyhon则可以相对简单些：
#
# @lc app=leetcode.cn id=53 lang=python3
#
# [53] 最大子序和
#
# https://leetcode-cn.com/problems/maximum-subarray/description/
#
# algorithms
# Easy (42.92%)
# Total Accepted: 39.9K
# Total Submissions: 93K
# Testcase Example: '[-2,1,-3,4,-1,2,1,-5,4]'
#
# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
#
# 示例:
#
# 输入: [-2,1,-3,4,-1,2,1,-5,4],
# 输出: 6
# 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
#
#
# 进阶:
#
# 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
#
#
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
length = len(nums)
for i in range(1,length):
Max = max(nums[i]+nums[i-1],nums[i])
nums[i]=Max
return max(nums)
这里在数组的循环中，当前值与前面的值得和进行比较，较大的存放到当前的nums数组中。
最后nums数组中存放的数都变成了各个阶段所求得的最大值，最后返回这些数的最大值即可。