子数组问题

子数组问题

• 最大子数组和
• 环形子数组的最大和
• 乘积最大的子数组
• 乘积为正数的最长子数组长度
• 等差数列划分
• 单词拆分
• 环绕字符串中唯一的子字符串

最大子数组和

题目解析：找出数组中和最大的子数组，并返回最大和 动态规划 状态表示：dp[i]表示以i位置为结尾的最大子数组和 状态转移方程：dp[i] = Math.max(nums[i ], dp[i – 1] + nums[i ]); 初始化：dp[0] = 0 或者引入一个虚拟位置，dp从1下标开始 填表顺序：从左到右 返回值：dp表中的最大值

class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[0] = 0;
int ret = –Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
dp[i] = Math.max(nums[i – 1], dp[i – 1] + nums[i – 1]);
ret = Math.max(ret, dp[i]);
}
return ret;
}
}

环形子数组的最大和

题目解析：找出数组中的连续子数组的最大和，并返回最大和，数组是环形(首尾相连)，将其分为两种情况 1和上题不是环形的一样，正常找出的连续子数组的最大和 2.利用了环形性质，找出连续子数组的最小和，sum-min就是其对应最大和 动态规划 状态表示： f[i]表示以i位置为结尾的最大子数组和 g[i]表示以i位置为结尾的最小子数组和 状态转移方程： f[i] = Math.max(nums[i ], f[i – 1] + nums[i ]); g[i] = Math.max(nums[i ], g[i – 1] + nums[i ]); 初始化： f[0] = g[0] = nums[0] 或者引入虚拟节点f[0] = g[0] = 0,此时与nums数组下标对应关系有所改变 填表顺序：从左到右 返回值：Math.max(fmax,sum – gmin)

//不使用虚拟节点
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int sum = 0;
int fmax = Integer.MIN_VALUE;
int gmin = Integer.MAX_VALUE;
int[] f = new int[n];//最大值
int[] g = new int[n];//最小值
//初始化
f[0] = g[0] = nums[0];
sum += nums[0];
fmax = Math.max(fmax,f[0]);
gmin = Math.min(gmin,g[0]);
for(int i = 1;i < n;i++){

f[i] = Math.max(nums[i],f[i–1] + nums[i]);
g[i] = Math.min(nums[i],g[i–1] + nums[i]);

sum += nums[i];
fmax = Math.max(fmax,f[i]);
gmin = Math.min(gmin,g[i]);
}
//可能数组全是负数，这样直接返回fmax即可
return gmin == sum ? fmax : Math.max(fmax,sum – gmin);
}
}

class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int sum = 0;
int fmax = Integer.MIN_VALUE;
int gmin = Integer.MAX_VALUE;
int[] f = new int[n+1];//最大值
int[] g = new int[n+1];//最小值
for(int i = 1;i <= n;i++){
f[i] = Math.max(nums[i–1],f[i–1] + nums[i–1]);
g[i] = Math.min(nums[i–1],g[i–1] + nums[i–1]);
sum += nums[i–1];
fmax = Math.max(fmax,f[i]);
gmin = Math.min(gmin,g[i]);
}
//可能数组全是负数，这样直接返回fmax即可
return gmin == sum ? fmax : Math.max(fmax,sum – gmin);
}
}

乘积最大的子数组

题目解析：找出数组中最大连续子数组积 数组中是有负数的，使用一个dp表表示以i位置为结尾的最大子数组积是不够的，因为负负得正，当前数是一个负数，从前面找一个最小的子数组积，此时才是最大的 动态规划 状态表示： f[i]表示以i位置为结尾的最大连续子数组积 g[i]表示以i位置为结尾的最小连续子数组积 状态转移方程： f[i] = max(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i]) g[i] = min(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i]) 初始化： 引入虚拟节点f[0] = g[0] = 1,此时与nums数组下标对应关系有所改变 填表顺序：从左到右 返回值：f表中的最大值

class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];
int[] g = new int[n+1];

f[0] = g[0] = 1;
int ret = Integer.MIN_VALUE;
for(int i = 1;i <= n;i++){
int x = nums[i–1];
int y = f[i–1] * nums[i–1];
int z = g[i–1] * nums[i–1];
f[i] = Math.max(Math.max(x,y),z);
g[i] = Math.min(Math.min(x,y),z);
ret = Math.max(f[i],ret);
}
return ret;
}
}

乘积为正数的最长子数组长度

题目解析：乘积为正的连续子数组最长长度 动态规划 状态表示： f[i]表示以i位置为结尾的乘积为正的最长子数组长度 g[i]表示以i位置为结尾的乘积为负的最长子数组长度 状态转移方程： nums[i] > 0 f[i] = f[i-1] + 1; g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1; nums[i] < 0 f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1; g[i] = f[i-1] + 1; 初始化： 引入虚拟节点f[0] = g[0] = 1,此时与nums数组下标对应关系有所改变 填表顺序：从左到右 返回值：f表中的最大值

class Solution {
public int getMaxLen(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];
int[] g = new int[n+1];
int ret = Integer.MIN_VALUE;
for(int i = 1;i <= n;i++){
if(nums[i–1] > 0){
f[i] = f[i–1] + 1;
g[i] = g[i–1] == 0 ? 0 : g[i–1] + 1;
}else if(nums[i–1] <0){
f[i] = g[i–1] == 0 ? 0 : g[i–1] + 1;
g[i] = f[i–1] + 1;
}
ret = Math.max(ret,f[i]);
}
return ret;
}
}

等差数列划分

题目解析：求出一个数组中连续子数组可以构成等差数列的个数 动态规划 状态表示： dp[i]：以i位置结尾的连续子数组为等差数列的个数 状态转移方程： dp[i] = nums[i] – nums[i-1] == nums[i-1] – nums[i-2] ? dp[i-1] + 1 : 0; 初始化： dp[0] = dp[1] = 0 填表顺序：从左到右 返回值：f表中总和

class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int ret = 0;
int n = nums.length;
int[] dp = new int[n];

for(int i = 2; i < n;i++){
dp[i] = nums[i] – nums[i–1] == nums[i–1] – nums[i–2] ? dp[i–1] + 1 : 0;
ret += dp[i];
}
return ret;
}
}

题目解析：求连续湍流子数组的最长长度 动态规划 状态表示： f[i]表示以i位置为结尾的最后呈现"上升"趋势最长湍流子数组长度 g[i]表示以i位置为结尾的最后呈现"下降"趋势最长湍流子数组长度 状态转移方程： f[i] = g[i] = 1 if (arr[i] > arr[i – 1]) { f[i] = g[i – 1] + 1; } else if (arr[i] < arr[i – 1]) { g[i] = f[i – 1] + 1; } 初始化： 可以将所有f表和g表全部初始为1 填表顺序：从左到右 返回值：f和g表中最大值

class Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int[] f = new int[n];
int[] g = new int[n];
//因为这里最小是1，可以将f表和g表全部初始化为1
for (int i = 0; i < n; i++) {
f[i] = g[i] = 1;
}
int ret = 1;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i – 1]) {
f[i] = g[i – 1] + 1;
} else if (arr[i] < arr[i – 1]) {

g[i] = f[i – 1] + 1;
}
ret = Math.max(Math.max(f[i], g[i]), ret);
}
return ret;
}
}

//不将其全部初始为1
//进入循环，可以先将其初始化为1，符合湍流条件进行更新
class Solution {
public int maxTurbulenceSize(int[] arr) {
int n = arr.length;
int[] f = new int[n];
int[] g = new int[n];
int ret = 1;
f[0] = g[0] = 1;
for (int i = 1; i < n; i++) {
//不符合表的特征，为1
f[i] = g[i] = 1;
if (arr[i] > arr[i – 1]) {
f[i] = g[i – 1] + 1;
} else if (arr[i] < arr[i – 1]) {
g[i] = f[i – 1] + 1;
}
ret = Math.max(Math.max(f[i], g[i]), ret);
}
return ret;
}
}

单词拆分

题目解析：给一个s字符串和一个字典，判断利用字典中的单词是否可以拼接处s这个字符串(字典中单词可以重复使用) 动态规划 状态表示： 布尔类型 dp[i]：s字符串[0,i]区间是否可以使用字典中单词拼接而成 状态转移方程： 判断[0,i]区间字符串是否可以被拼接而成，可以将其分为两部分[0,j-1]和[j,i] j的取值范围[0,i] 条件1 ：[0,j-1] – > dp[j-1] 条件2：[j,i] – > 判断s字符串中是否存在这个单词 当条件1和2都满足，此时dp[i]是true，如果所有情况都不满足返回false 初始化： 引入一个虚拟节点 dp[0] = true 填表顺序：从左到右 返回值：dp[i]

细节优化
优化1：可以使用一个哈希表将字典中单词放入，方便查找一个单词是否在字典中
优化2：dp表引入了虚拟节点，下标对应关系和s字符串有所改变
可以让s = " "+s将字符串s向后移动一个位置,这样下标就一一对应

class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> hash = new HashSet<>(wordDict);
int n = s.length();
boolean[] dp = new boolean[n+1];
s = " " + s;//方便处理下标映射关系
dp[0] = true;
for(int i = 1;i <= n;i++){
for(int j = i;j >= 1;j—){
//[1,j-1] -> dp[j-1]为true
//&& [j,i]存在字典中
if(dp[j–1] && hash.contains(s.substring(j,i+1))){
dp[i] = true;
break;
}
}
}

return dp[n];
}
}

环绕字符串中唯一的子字符串

题目解析：有一个base字符串，其是abcdef…………xyzabce……26个小写字母无限环绕的字符串，给了一个字符串s,求s中有多少不同的子串在base出现 动态规划 状态表示 dp[i] : 以i位置的元素结尾的，有多少子串存在base中 状态转移方程 dp[i]的值为 以i元素结尾子串长度为1 + 子串长度>1之和 dp[i] = 1 + dp[i-1]（前提是s[i-1] 和 s[i]是连续的） 初始化 可以将dp表中都现初始化为1，因为其长度为1都是在base中的，此时这里状态转移方程变成 dp[i] += dp[i-1]（满足条件才进行相加） 填表顺序 从左到右 返回值 不可以直接返回dp表所有值之和，因为有重复 因为以同一字符结尾dp值，肯定更长的dp值更大，并且其是包含相同结尾较短字符中的所有情况，所以此时直接返回所有字符结尾中dp表中最大值 此时可以使用一个26数组统计对应以某个字符结尾的最大结果即可

class Solution {
public int findSubstringInWraproundString(String ss) {
char[] s = ss.toCharArray();
int n = ss.length();
int[] hash = new int[26];//以这个字符结尾有多少子串在环绕字符串中
int[] dp = new int[n];
//此时这里都是由小写字母组成，单个字符肯定符合
for(int i = 0; i < n;i++){
dp[i] = 1;
}
hash[s[0] – 'a'] = 1;
for(int i = 1;i < n;i++){
if(s[i–1] + 1 == s[i] || (s[i–1] == 'z' && s[i] == 'a')){
dp[i] += dp[i–1];
}
//更新哈希表(去重)
hash[s[i] – 'a'] = Math.max(dp[i],hash[s[i] – 'a']);
}

int ret = 0;
for(int i = 0;i < 26;i++){
ret += hash[i];
}
return ret;
}
}