class Interval {
    int buy;
    int sell;
}

class Solution{
    //Function to find the days of buying and selling stock for max profit.
    ArrayList<ArrayList<Integer> > stockBuySell(int A[], int n) {
        
        ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
      //Prices must be given for at least two days else return the empty result.
        if(n==1){
            return result;
        }
        
        //Creating solution vector.
        ArrayList<Interval> sol = new ArrayList<Interval>();
        int i=0, cnt=0;
        //Traversing through given price array.
        while (i < n-1) {
            //Finding Local Minima. Note that the limit of loop is (n-2)
            //as we are comparing present element to the next element.
            while ((i < n-1) && (A[i+1] <= A[i])){
                i++;
            }
            //If we reach the end, we break loop as no further 
            //solution is possible.
            if (i == n-1){
                break;
            }
            Interval e = new Interval();
            //Storing the index of minima which gives the day of buying stock.
            e.buy = i++;
 
            //Finding Local Maxima. Note that the limit of loop is (n-1)
            //as we are comparing present element to previous element.
            while ((i < n) && (A[i] >= A[i-1]))
                i++;
 
            //Storing the index of maxima which gives the day of selling stock.
            e.sell = i-1;
            sol.add(e);
            //Incrementing count of buy/sell pairs.
            cnt++;
        }
        if(cnt==0){
            return result;
        } else {
            //Storing the buy/sell pairs in a list.
            for(int j=0; j<sol.size(); j++){
                result.add(new ArrayList<Integer>()); 
                result.get(j).add(0, sol.get(j).buy);
                result.get(j).add(1, sol.get(j).sell);
            }
        }
        //returning the result.
        return result;
    } 
    
}

// Efficient Method : Time Complexity : O(n), Auxilliary Space : O(n)

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	int lMax[] = new int[n];
    	int rMax[] = new int[n];

    	lMax[0] = arr[0];
    	for(int i = 1; i < n; i++)
    		lMax[i] = Math.max(arr[i], lMax[i - 1]);


    	rMax[n - 1] = arr[n - 1];
    	for(int i = n - 2; i >= 0; i--)
    		rMax[i] = Math.max(arr[i], rMax[i + 1]);

    	for(int i = 1; i < n - 1; i++)
    		res = res + (Math.min(lMax[i], rMax[i]) - arr[i]);
    	
    	return res;
    }


    public static void main(String args[]) 
    { 
       int arr[] = {5, 0, 6, 2, 3}, n = 5;

      System.out.println( getWater(arr, n)); // Output : 6
    } 
}


// Naive Method : Time Complexity : O(n^2)

    static int getWater(int arr[], int n)
    {
    	int res = 0;

    	for(int i = 1; i < n - 1; i++)
    	{
    		int lMax = arr[i];

    		for(int j = 0; j < i; j++)
    			lMax = Math.max(lMax, arr[j]);

    		int rMax = arr[i];

    		for(int j = i + 1; j < n; j++)
    			rMax = Math.max(rMax, arr[j]);

    		res = res + (Math.min(lMax, rMax) - arr[i]);
    	}
    
    	return res; // Output : 6
    }

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int n)
    {
    	int profit = 0;

    	for(int i = 1; i < n; i++)
    	{
    		if(price[i] > price[i - 1])
    			profit += price[i] - price[i -1];
    	}
    
    	return profit;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {1, 5, 3, 8, 12}, n = 5;

       System.out.println(maxProfit(arr, n));
    } 
}

import java.util.*;
import java.io.*;

class GFG 
{ 
    static int maxProfit(int price[], int start, int end)
    {
    	if(end <= start)
    		return 0;

    	int profit = 0;

    	for(int i = start; i < end; i++)
    	{
    		for(int j = i + 1; j <= end; j++)
    		{
    			if(price[j] > price[i])
    			{
    				int curr_profit = price[j] - price[i] 
    								  + maxProfit(price, start, i - 1)
    								  + maxProfit(price, j + 1, end);

    				profit = Math.max(profit, curr_profit);
    			}
    		}
    	}

    	return profit;
    }

    public static void main(String args[]) 
    { 
       int arr[] = {1, 5, 3, 8, 12}, n = 5;

       System.out.println(maxProfit(arr, 0, n-1));
    } 
}