偏爱字母

[编程题]偏爱字母

热度指数：3827 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美喜欢字母E，讨厌字母F。在小美生日时，小团送了小美一个仅包含字母E和F的字符串，小美想从中选出一个包含字母E数量与字母F数量之差最大的子串。

*子串：从字符串前面连续删去若干个字符，从后面连续删去若干个字符剩下的字符串（也可以一个都不删），例如abcab是fabcab的子串，而不是abcad的子串。我们将空串看作所有字符串的子串。

输入描述:

第一行一个正整数n表示字符串的长度。

第二行长度为n，且仅包含大写字母’E’,’F’的字符串（不含引号）

输出描述:

输出一个整数，表示最大的差值

示例1

输入

5
EFEEF

输出

说明

选择子串EE,此时有2个E，0个F,有最大差值2-0=2

另外，选择子串EFEE也可以达到最大差值。

备注:

对于30%的数据，n<=300
对于60%的数据，n<=3000
对于100%的数据，n<=300000

算法知识视频讲解

JavaScript

牛客68020592号

看到“最大“的字样想到动态规划
先将EF字符串转换为1,-1的数组nums
然后明确dp，dp[i]代表以nums[i]结尾的子串的最大和
明确dp方程，dp[i]由前一项和nums[i]决定，如果前一项小于0，则去掉前面的项

得出dp方程，即dp[i] = Math.max(dp[i-1], 0) + nums[i]

初始化dp，由方程已知，初始化dp[0]即可，得出dp[0] = nums[0]

把每次得到的最大和进行对比，求出最大和max

// 动态规划
let n = ~~readline()
let str = readline().split('')
let dp = []
// 将EF替换为1，-1
let nums = str.map(item => item == 'E' ? 1 : -1)
// 初始化dp数组
dp[0] = nums[0]
// 初始化最大差值
let max = nums[0]
for(let i = 1 ;i<n;i++){
    dp[i] = Math.max(dp[i-1], 0) + nums[i]
    max = Math.max(dp[i] ,max)
}
// 依据题意，差值最小时为全F的情况，输出0
print(max >= 0 ? max : 0)

编辑于 2022-03-12 11:54:22 回复(0)

JavaScript

古拳法大师兄

let len = parseInt(readline())
let str = readline()

function findmax (str) {
  let initindex = str.indexOf('E')
  if (initindex == -1) return 0
  let dp = new Array(len - initindex).fill(1)
  let diff = 1
  for (let i = initindex + 1; i < len; i++) {
    diff = str[i] == "E" ? diff + 1 : diff - 1
    if (diff < 0) diff = 0
    dp[i - initindex] = Math.max(dp[i - initindex - 1], diff)
  }
  return dp[dp.length - 1]
}
print(findmax(str))

发表于 2021-03-19 00:02:32 回复(0)