议事大厅-【赛码网】..

第二题

动态规划 

//最小值
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);
            }
           
        }

2017-08-23 00:09

coder_UmhiVW2j

import java.util.Scanner;
/**
 * 头条笔试二题思路,未测试是否AC,仅供交流学习,有问题恳请指出,谢谢!
 * 指定条件的最小子集合
 * 集合包含顺序,是连续子数组;
 * 条件:使得子数组中最小的数和数组元素之和的乘积最大,找出这样的最大乘积,不要求输出具体数组
 * 每个元素大小0-100
 * 数组个数n,n为0-500000
 * 测试数据
 * 3
 * 6 1 2
 * 输出36
 *
 * 分析算法复杂度n^2肯定超时,也就是最笨的顺序搜索
 * 思路一:
 * 定义等待寻找的数组为目标数组,目标数组的乘积最大.
 * 找到数组中最小的元素,如果他是目标数组的最小元素,则这个目标数组应该是整个数组.可论证min不变,sum越大越好,记录下此时的乘积
 * 如果他不是目标数组的最小值,那么目标数组在这个最小元素的左右两侧之一
 * 对左右两侧数组进行相同的搜索.
 * 搜索完成后,得到了每个元素作为数组最小元素时候的最大乘积,其中最大的就是answer
 *时间复杂度分析,必须递归搜到数组为1的情况结束,每次都需要计算数组和以及乘积,同时还要找到左右两侧的最小值进行下一次递归
 * 递归次数:假设最好情况均匀(最小值在中间)logn,最坏情况,假设是递全减递增的,为n.
 * 最好的时候,每一层计算量是:2n,2n-1..2n-logn,最坏的情况下,每一层为n,n-1...1
 * 最好的情况是2nlogn,最坏的情况是n^2/2;
 *
 * 思路二
 * 10 9 8 7=34*7
 */
public class Main {
    static long ans=0;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            doMain(scanner);
        }
    }
    private static void doMain(Scanner scanner) {
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        search(nums,0,n-1);
        System.out.println(ans);
    }
    private static void search(int[] subArry,int x,int y){
        //求和,顺便求出最小值
        int sum=0;
        int min=Integer.MAX_VALUE;
        int minIndex=x;
        for(int i=x;i<=y;i++){
            if(min>subArry[i]){
                min=subArry[i];
                minIndex=i;
            }
            sum+=subArry[i];
        }
        long t=sum*min;
        //记录最大值
        if(ans<t){
            ans=t;
        }
        if(y-x>0){
            //边界
            if(minIndex==x) {
                search(subArry,x+1,y );
                return;
            }
            if(minIndex==y){
                search(subArry,x,y-1);
                return;
            }
            search(subArry,x,minIndex-1);
            search(subArry,minIndex+1,y);
        }
    }
}

2017-08-23 02:48

coder_QsfnpyO3

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int N = in.nextInt();
			int[][] nums = new int[N][2];
			for(int i=0; i<N; i++){
				nums[i][0] = in.nextInt();
				nums[i][1] = in.nextInt();
			}
			// 按照x倒序排序
			Arrays.sort(nums,new Comparator<int[]>(){
				[@Override](/user/Override)
				public int compare(int[] o1, int[] o2) {
					return o2[0]-o1[0];
				}
			});
			//以x倒序后的第一个坐标y为基准，找y的递增序列
			Stack<int[]> res = new Stack<int[]>();
			res.add(nums[0]);
			int min = nums[0][1];
			for(int i=1; i<N; i++){
				if(nums[i][1] > min){
					res.add(nums[i]);
					min = nums[i][1];
				}
			}
			while(!res.isEmpty()){
				int[] num = res.pop();
				System.out.println(num[0]+" "+num[1]);
			}
		}
		in.close();
	}
}

只有70%，显示超时，问题出在哪儿？

2017-08-23 10:16