剑指offer刷题（算法类_1） 斐波那契数列 搜索算法 全排列 动态规划 回溯
007-斐波拉契数列
题目描述
题解
代码
复杂度
008-跳台阶
题目描述
题解
代码
复杂度
009-变态跳台阶
题目描述
题解
代码
复杂度
010-矩形覆盖
题目描述
题解
代码
复杂度
搜索算法
001-二维数组查找
题目描述
题解
代码
复杂度
006-旋转数组的最小数字（二分查找）
题目描述
题解
代码
复杂度
037-数字在排序数组中出现的次数（二分查找）
题目描述
题解
代码
复杂度
全排列
027-字符串的排列动态规划
题目描述
题解
代码
复杂度
052-正则表达式匹配
题目描述
题解
代码
复杂度
动态规划
030 连续子数组的最大和
题目描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
- 要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
- 1 <= arr.length <= 10^5
- -100 <= arr[i] <= 100
题解
1.定义一个 sum , res
2.遍历数组
- 若当前的sum < 0 , sum = 遍历的数， else sum = sum + 遍历的数；
- 比较 res 和 sum 的最大值 赋给 res；
代码
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int len = array.length;
if (len == 0) return 0;
int sum = array[0], res = sum;
for(int i = 1; i < len; i++){
if(sum > 0){
sum = sum + array[i];
}else{
sum = array[i];
}
res = Math.max(sum,res);
}
return res;
}
}
复杂度
- 时间复杂度 O(N) ： 线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
空间复杂度 O(1) ： 使用常数大小的额外空间。