public class Solution {
public static void main(String[] args) {
int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
// System.out.println(containsDuplicate(nums));
System.out.println(maxSubArray(nums));
}
/**
* 给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和,子数组是数组中的一个连续部分
*
* @param nums
* @return
*/
public static int maxSubArray(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count += nums[i];
//取区间累计的最大值(相当于不断确定最大子序终止位置)
sum = Math.max(sum, count);
if (count <= 0) {
//相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
count = 0;
}
}
return sum;
}
}
评论