range dp

import java.util.*;

/*

given an array of N integers task is to find the max sum , twist is you are given an integer x and pick a range of elements
and multiply the elements to get max sum .


 */
/**
 important point to understand here -

here x is an integer that means
x can also be negative

lets assume you are given an array
 0  1 2 3 4   5//indices
-1 -2 3 4 5 -10

and an integer x as -10

lets solve this using dp
at any point of time
your arr[i] can be part of multiplcation or need not to be , so you need to consider both the situations

when arr[i] is a part of multiplcation 2 possibilities
this multiplication is started long back and still continuing
yyyxx
or
this multiplication is just started now
yyyyx

when arr[i] is not a part of multiplcation 3 possibilities
this multiplication is never happened
yyyyy
or
this multiplication is ended just now
yyxxy
or
this multiplication is ended long time back
xxyyy

 */
 /*

//inputs for array and given an x
-1 -2 3 4 5 -10
-10

expected output -
The result is 112


 */


@SuppressWarnings("unused")
public class A20250122_RubrikOA {

    static Scanner sc = new Scanner(System.in);

    private static int[] getArray() {
        String[] sArr = sc.nextLine().split(" ");
        int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
        return arr;
    }

    private static char[] getCharArray() {
        String[] sArr = sc.nextLine().split(" ");
        char[] cArr = new char[sArr.length];
        for (int i = 0; i < sArr.length; i++) {
            cArr[i] = sArr[i].charAt(0); // Take the first character of each string
        }
        return cArr;
    }

    private static int getMax(int[] arr) {
        int currMax = Integer.MIN_VALUE;
        for (int curr : arr) {
            currMax = Math.max(currMax, curr);
        }
        return currMax;
    }

    public static void main(String args[]) {
        // prepare the inputs

        int[] arr = getArray();
        int arrLen = arr.length;
        int lastIndex = arrLen - 1;
        int x = getArray()[0];
        int[] kadane = new int[arrLen];//this helps to give best possible sum , without any multiplication
        int sum =0;
        //fill the kadane
        for(int i =0;i<arrLen;i+=1){
            sum = getMax(new int[]{
                0,//make 0 if sum is becoming negative when involving curr element
            arr[i],//considering the case if the sum be starting with current element
            arr[i]+sum//considering the incoming best sum
            });

            kadane[i] = sum;
        }

        //initialize the dp
        int[][] dp = new int[arrLen][2];//for every case we need to see wether if current involved in multiplication or if not involved in multiplication
        //0 for not involved , 1 for involved
        //atleast 0 index should be filled manually

        dp[0][0] = getMax(new int[]{0,arr[0]});
        dp[0][1] = getMax(new int[]{0,arr[0]*x});
        int maxi = Integer.MIN_VALUE;
        for(int i =1;i<arrLen;i+=1){
            //if not involved
            dp[i][0] = getMax(new int[]{
                0,arr[i],
                arr[i]+dp[i-1][0],//multiplication previously long back ended
                arr[i]+dp[i-1][1],//multiplication just now ended
                arr[i]+kadane[i-1]//multiplication never happened ,[imp] case
            });

            //if involved
            dp[i][1] = getMax(new int[]{
                0,arr[i]*x,
                arr[i]*x+dp[i-1][1],//multiplication started from long back
                arr[i]*x+kadane[i-1]//multiplication just now started
            });

            maxi = getMax(new int[]{maxi , dp[i][0], dp[i][1]});
        }



        int ans = maxi;



        int res = ans;

        System.out.println("The result is " + res);

    }
}

class Pair{
    int row;
    int col;
    public Pair(int i,int j){
        this.row = i;
        this.col = j;

    }
}