今日头条编程第二题的两种解法

动态规划

枚举以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);
            }
        }

#字节跳动#