pick a range and replace from 2nd array to get max sum subarr in 1st

import java.util.*;

/*

given 2 array of N size integers task is to find the max sum of arrA, twist is you can pick a range of elements from 2nd arr
and replace the same index elements in 1st array to get max sum .


 */
/**
 important point to understand here -



lets assume you are given 2 arrays

-100  -20  10  -100  -1000//arrA
-100 -200 -100  100  -1000//arrB



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

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

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

 */
 /*

//inputs for 2 arrays
-100 -20 10 -100 -1000
-100 -200 -100 100 -1000

expected output -
The result is 110


 */


@SuppressWarnings("unused")
public class A20250123_GoogleOA  {

    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[] arrA = getArray();
        int[] arrB = getArray();
        int arrLen = arrA.length;

        int lastIndex = arrLen - 1;
        int[] kadane = new int[arrLen];//this helps to give best possible sum , without any replacement
        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
            arrA[i],//considering the case if the sum be starting with current element
            arrA[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 replacement or if not involved in replacement
        //0 for not involved , 1 for involved
        //atleast 0 index should be filled manually

        dp[0][0] = getMax(new int[]{0,arrA[0]});
        dp[0][1] = getMax(new int[]{0,arrB[0]});
        int maxi = Integer.MIN_VALUE;

        for(int i =1;i<arrLen;i+=1){
            //if not involved
            dp[i][0] = getMax(new int[]{
                0,arrA[i],
                arrA[i]+dp[i-1][0],//replacement previously long back ended
                arrA[i]+dp[i-1][1],//replacement just now ended
                arrA[i]+kadane[i-1]//replacement never happened ,[imp] case
            });

            //if involved
            dp[i][1] = getMax(new int[]{
                0,arrB[i],
                arrB[i]+dp[i-1][1],//replacement started from long back
                arrB[i]+kadane[i-1]//replacement 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;

    }
}