网易2017笔试－合唱团

题目https://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8

题目重述

一排数字，可正可负；从前往后，挑出K个；可有间隔，不超过D;
K个数字，最大乘积，到底多少．

想法

不会．．．参考的．
如果这写数字全部都是正的或者是负的，那就比较好办了．问题是有正有负难度就比较大了．现在令两个dp数组出来，maxdp[k][i]表示挑出k个数字，且以第i个数字结尾的最大乘积，同理mindp[k][i]表示挑出k个数字，且以第i个数字结尾的最小乘积．
那么现在考虑maxdp[k+1][i] ,代表以第i个数字结尾，挑出k+1个数字的最大乘积，但是i位前面一个数字的位置是不确定的，这就需要一个前向遍历,令前向遍历的下标为j,则罗列出所有maxdp[k][j] * vec[i]的值挑选一个最大的就是maxdp[k+1][i]了，真的是这样吗？ naive!　还需要考虑可能负数的情况，这部分实现参考代码部分，其实就是把mindp[k][j]*vec[i]情况考虑下然后比较谁大．mindp[k][?]在执行过程中的作用可以理解为为maxdp[k+1][?]产生铺垫，最终找出maxdp[K][0~(n-1)]的值就是最终答案(这里的大写的K代表输入K).

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
inline long long max(long long a,long long b){return (a>b?a:b);}
inline long long min(long long a,long long b){return (a>b?b:a);}
int main()
{
  int n,K,d;
  scanf("%d", &n);
  vector<long long int> vec;
  vec.resize(n+1);
  for(int i=0;i<n;i++) scanf("%lld", &vec[i]);
  scanf("%d %d",&K, &d);
  long long int ans = -1;
  long long maxdp[11][51];
  long long mindp[11][51];
  for(int i=1;i<=K;i++)
    for(int j=0;j<n;j++ ) maxdp[i][j]=mindp[i][j]=0;
  for(int i=0;i<n;i++){
    maxdp[1][i] = mindp[1][i] = vec[i];
    for(int k=2;k<=K;k++){
      // 前向遍历，同时注意条件 i-j<d
       for(int j=i-1; j>=0 && i-j<d; j--){
         maxdp[k][i] = max(max(maxdp[k-1][j]*vec[i],mindp[k-1][j]*vec[i]),maxdp[k][i]);
         mindp[k][i] = min(min(mindp[k-1][j]*vec[i],maxdp[k-1][j]*vec[i]),mindp[k][i]);
       }
    }
    ans = max(maxdp[K][i],ans);
  }
  printf("%lld\n",ans);
  return 0;
}