ABC-125-D Flipping Signs

■■■問題■■■

N個の整数が並んでおり、順に A1,A2, ・・・ , ANです。
あなたは、この整数列に対して次の操作を好きなだけ行うことができます。

操作: 1 <= i <= N - 1を満たす整数iを選ぶ。AiとAi+1 に -1を乗算する。

操作終了後の整数列を B1 , B2 , ・・・ , BNとします。
B1 + B2 + ・・・ + BN の最大値を求めてください。

■■■入力■■■

N
A1 A2 ・・・ AN

●入力は全て整数である
●2 <= N <= 10万
●-10億 <= Ai <= 10億

■■■出力■■■

B1 + B2 + ・・・ + BN の最大値を出力せよ。

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("3");
            WillReturn.Add("-10 5 -4");
            //19
            //次のように操作を行うと、B1=10 , B2=5 , B3=4 になり、
            //このときの B1+B2+B3 = 10+5+4 = 19 が最大です。
            //●iとして1を選ぶ。操作により、整数列は 10,-5,-4に変化する。
            //●iとして2を選ぶ。操作により、整数列は 10,5,4に変化する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("10 -4 -8 -11 3");
            //30
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000");
            //10000000000
            //出力が32ビット整数型に収まらない場合があります
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        //負数の数
        int MinusCnt = AArr.Count(X => X < 0);

        //絶対値の最小値
        int MinABS = AArr.Min(X => Math.Abs(X));

        long SumABS = 0;
        Array.ForEach(AArr, X => SumABS += Math.Abs(X));

        //負数が偶数個の場合
        if (MinusCnt % 2 == 0) {
            Console.WriteLine(SumABS);
        }
        else { //負数が奇数個の場合
            Console.WriteLine(SumABS - MinABS * 2);
        }
    }
}

解説

下記の考察をふまえて、負数の個数で場合分けしてます。

●負数が偶数個なら、全ての符号をプラスにするのが最善。
●負数が奇数個なら、絶対値が最小の数値をマイナスにするのが最善。