ARC174-A A Multiply

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 2");
            WillReturn.Add("-10 10 20 30 -20");
            //90
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 1000000");
            WillReturn.Add("-1 -2 -3 -4 -5");
            //-15
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 -1");
            WillReturn.Add("-9 9 -8 2 -4 4 -3 5 -3");
            //13
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;
    static long UB;

    static long mProd;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mProd = wkArr[1];

        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        UB = mAArr.GetUpperBound(0);

        long DefaultSum = mAArr.Sum();

        var AnswerKouhoList = new List<long>();
        AnswerKouhoList.Add(DefaultSum);

        if (mProd > 0) {
            long ResultDP = ExecDP_Plus();
            AnswerKouhoList.Add(DefaultSum - ResultDP + ResultDP * mProd);
        }
        if (mProd <= 0) {
            long ResultDP = ExecDP_Minus();
            AnswerKouhoList.Add(DefaultSum - ResultDP + ResultDP * mProd);
        }
        Console.WriteLine(AnswerKouhoList.Max());
    }

    // Prodが+の場合のDP結果を返す
    static long ExecDP_Plus()
    {
        // 最大値
        var PrevDP = new List<long>();
        PrevDP.Add(0);

        long Answer = 0;

        foreach (long EachA in mAArr) {
            var CurrDP = new List<long>();
            CurrDP.Add(0);

            foreach (long EachSunSum in PrevDP.OrderByDescending(pX => pX).Take(1)) {
                long NewVal = EachSunSum + EachA;
                if (NewVal <= 0) continue;

                CurrDP.Add(NewVal);
                Answer = Math.Max(Answer, NewVal);
            }
            PrevDP = CurrDP;
        }
        return Answer;
    }

    // Prodが-の場合のDP結果を返す
    static long ExecDP_Minus()
    {
        // 最小値
        var PrevDP = new List<long>();
        PrevDP.Add(0);

        long Answer = 0;

        foreach (long EachA in mAArr) {
            var CurrDP = new List<long>();
            CurrDP.Add(0);

            foreach (long EachSunSum in PrevDP.OrderBy(pX => pX).Take(1)) {
                long NewVal = EachSunSum + EachA;
                if (NewVal >= 0) continue;

                CurrDP.Add(NewVal);
                Answer = Math.Min(Answer, NewVal);
            }
            PrevDP = CurrDP;
        }
        return Answer;
    }
}

解説

-9 9 -8 2 -4 4 -3 5 -3
で考えると

Prodが1以上なら
選択する区間に上限が無いので、
状態に左からの累積和の最大値を持ち、DPすれば良いです。
DPでの遷移元は、最大値のみを使うようにすれば良いです。
(Select文でOrderByとLimit 1 を組み合わせる感覚)

Prodが0以下なら
選択する区間に上限が無いので、
状態に左からの累積和の最小値を持ち、DPすれば良いです。
DPでの遷移元は、最小値のみを使うようにすれば良いです。
(Select文でOrderByとLimit 1 を組み合わせる感覚)