今日头条编程第二题的两种解法
动态规划
枚举以i开始序列长度为l的最小值算序列积
F[i][l] 以i开始的长度为l的最小值
//最小值
F[i][l] = min{F[i][l-1],A[i+l-1]}
result = max{F[i][l] *(sum[i+l-1]-sum[i-1]) | 1≤i≤n}
public static void Main()
{
string line;
string[] p;
int n = 0;
while((line = Console.ReadLine())!=null){
p = line.Split(' ');
n = Convert.ToInt32(p[0]);
int[] sum = new int[n+1];
int[] A = new int[n + 1];
int[,] v_min = new int[n + 1, n + 1];
sum[0] = 0;
p = Console.ReadLine().Split(' ');
for(int i=1;i <= n;i++){
A[i] = Convert.ToInt32(p[i - 1]);
sum[i] = sum[i - 1] + A[i];
}
int max = -1;
for(int i=1;i<=n;i++){
for(int l=1;l <= n - i + 1;l++){
if(l == 1){
v_min[i, l] = A[i];
}
else{
if(A[ l + i - 1] < v_min[i,l-1] ){
v_min[i, l] = A[l + i - 1];
}
else{
v_min[i, l] = v_min[i, l - 1];
}
}
max = Math.Max(max ,v_min[i, l] * (sum[i + l - 1] - sum[i - 1]));
}
}
Console.WriteLine(max);
}
}
/*
* 把每个数字看成最小值,由于区间是[0,200]所以符合条件的区间越大值越高
* 找到这个数的左边界和右边界
* 最后把每个数字的序列积算出来取最大值
* r[i]：A[i]右边第一个小于A[i]的下标
* l[i]：A[I]左边一个小于A[I]的下标
* F(i) = max{ A[k] * (sum(r[k]) - sum(l[k]-1)) | k∈[1,i]}
*/
public static void Main()
{
string line;
string[] p;
int n = 0;
while ((line = Console.ReadLine()) != null){
p = line.Split(' ');
n = Convert.ToInt32(p[0]);
int[] sum = new int[n + 1];
int[] A = new int[n + 1];
int[] left = new int[n+1];
int[] right = new int[n + 1];
sum[0] = 0;
p = Console.ReadLine().Split(' ');
for (int i = 1; i <= n; i++){
A[i] = Convert.ToInt32(p[i - 1]);
sum[i] = sum[i - 1] + A[i];
}
for (int i = 1; i <= n;i++ ){ //找右边的边界
int j = i;
right[i] = n;
while(j<=n){
if (A[j] < A[i]){
right[i] = j-1;
break;
}
j++;
}
}
for (int i = n; i >= 1;i-- ){ //找左边的边界
int j = i;
left[i] = 1;
while(j>=1){
if (A[j] < A[i]){
left[i] = j + 1;
break;
}
j--;
}//while
}//for
int ans = -1;
for (int i = 1; i <= n;i++ ){
ans = Math.Max(ans,A[i] *( sum[right[i]] - sum[left[i]-1]));
}
Console.WriteLine(ans);
}
}
投递华为等公司10个岗位
