数组混淆点整理
不写代码 只讲思路
# 最大子数组和
1、先定义 pre 跟 max ，max用于返回， 初始值为nums[0];
2、for循环 迭代nums，
3、pre的值为 num 跟 pre+num取最大值
4、max的值为 max 跟 pre取最大值
5、结束
1
2
3
4
5
2
3
4
5
# 最大子数组乘积
1、先定义 max 用于返回 imax = 1 跟 imin = 1；
2、遍历nums
3、如果 num[i] < 0，imax 跟 imin 交换值
4、imax = max (imax * num[i], nums[i])
5、imin = min (imin * num[i], nums[i])
6、最后 imax 跟 max 取最大值赋值给max
7、返回max
1
2
3
4
5
6
7
2
3
4
5
6
7
# 无重复字符的最长子串 （滑动窗口）
1、 set判断
1
# 组合总和 （回溯）
# 最长递增子序列 （动态规划）
1、定义dp 填充
2、定义max用于返回
3、然后两层for 动态规划这边的第二层for一般都还是j<i 的（或者可能加其他的）
4、 if(nums[j]< nums[i]){dp[i] = Math.max(dp[i], dp[j]+1);} 记录
5、最后对比max跟dp[i] 取最大值
1
2
3
4
5
6
7
2
3
4
5
6
7
# 最长回文子串 （双层for 暴力破解）
# 最长公共子序列 （二维动态规划）
# 最长连续序列
class Solution {
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
Arrays.sort(nums);
Set<Integer> set = new LinkedHashSet<>();
for(int i : nums){
set.add(i);
}
int res = 1;
int start = 1;
int item = Integer.MIN_VALUE;
for(Integer i : set){
if(i- item == 1){
start++;
}else{
start = 1;
}
item = i;
res = Math.max(res, start);
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 最长连续递增序列
class Solution {
public int findLengthOfLCIS(int[] nums) {
int count = 1;
int res = 1;
for(int i = 0; i< nums.length-1;i++){
if(nums[i+1] > nums[i]){
count ++;
} else {
count = 1;
}
if(count > res){
res = count;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
上次更新: 2024/03/26, 9:03:00