连续子数组的最大和
题目:
思路:
先是说一说对这道题的理解吧,这题要么采用的是暴力破解方法,采用双循环的方式。
通过一层循环,决定起始位置,然后不断循环从起始位置加起用于存储最大值。
或者采用动态规划,寻找出规律F(N) = F(N-1) + A[N]
这种方法的时间复杂度为O(N),空间复杂度为O(N)。
代码示例:
public class Solution {
public static void main(String[] args) {
int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};
int result = FindGreatestSumOfSubArray(arr);
System.out.println(result);
}
public static int FindGreatestSumOfSubArray(int[] array) {
int len = array.length;
if (len == 0) {
return 0;
}
//用于存储动态规划的结果数组
int[] currentsum = new int[len];
currentsum[0] = array[0];
int maxsum = array[0];
for (int i = 1; i < len; i++) {
//利用F(N) = F(N-1) + A[N] 来记录以第i个数字结尾的子数组的最大和
//此外要记得如果F(N)<0,则下一次会直接拿A[N]赋值进去,因为如果是负数了,那么与后面的数相加只会起到变小作用
//此外,另用一个变量存储遇到的最大的连续子数组的和。
if (currentsum[i - 1] > 0) {
currentsum[i] = currentsum[i - 1] + array[i];
} else {
currentsum[i] = array[i];
}
if (currentsum[i] > maxsum) {
maxsum = currentsum[i];
}
}
return maxsum;
}
}
相关文章
- vue遍历数组对象foreach_js遍历对象数组
- 2022-08-22:给定一个数组arr,长度为n,最多可以删除一个连续子数组, 求剩下的数组,严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。
- 数组操作方法(包括es6数组的操作方法)[通俗易懂]
- jQuery数组反转「建议收藏」
- java 输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组
- Java输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。[通俗易懂]
- 【说站】python有哪些数组叠加函数
- java怎么给byte数组赋值_关于数组的问题
- 合并数组 【归并 或 思维】
- 153. 寻找旋转排序数组中的最小值
- 【Linux 内核 内存管理】分区伙伴分配器 ① ( 分区伙伴分配器源码数据结构 | free_area 空闲区域数组 | MAX_ORDER 宏定义 | 空闲区域的页最大阶数 )
- leetcode:数组中的第K个最大元素
- PHP array_key_exists():判断数组的键名或索引是否存在
- 多维度探索将多维数组存入Redis中(多维数组存redis)
- Redis存储复杂数据的佼佼者(redis能存数组么)
- php下几个常用的去空、分组、调试数组函数
- js常用数组操作方法简明总结
- C语言求连续最大子数组和的方法