53. 最大子序和
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [0]
输出:0
示例 4:
输入:nums = [-1]
输出:-1
示例 5:
输入:nums = [-100000]
输出:-100000
提示:
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
数组长度为N 子数组的数量为N*N
dp[i] 含义:子数组必须以i结尾的时候,所有可以得到的子数组中,最大累加和是多少?
class Solution {
public int maxSubArray(int[] nums) {
int N = nums.length;
// dp[i] 含义:子数组必须以i结尾的时候,所有可以得到的子数组中,最大累加和是多少?
int[] dp = new int[N];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < N; i++) {
int p1 = nums[i];
int p2 = nums[i] + dp[i - 1];
dp[i] = Math.max(p1, p2);
max = Math.max(max, dp[i]);
}
return max;
}
}
class Solution {
fun maxSubArray(nums: IntArray): Int {
val N = nums.size
val dp = IntArray(N)
dp[0] = nums[0]
var max = dp[0]
for (i in 1 until N) {
val p1 = nums[i]
val p2 = nums[i] + dp[i - 1]
dp[i] = Math.max(p1, p2)
max = Math.max(max, dp[i])
}
return max
}
}
class Solution {
fun maxSubArray(nums: IntArray):Int{
var result=Int.MIN_VALUE
var curMaxSubSum=0
for ( i in nums){
curMaxSubSum=Math.max(i,i+curMaxSubSum);
result=Math.max(curMaxSubSum,result)
}
return result;
}
}