Largest Pair of Points - Google Top Interview Questions


Problem Statement :


You are given a strictly increasing list of integers nums and a list of integers values, both of the same length. 
Find a pair i ≤ j that maximizes values[i] + values[j] + nums[j] - nums[i] and return the value.

Constraints

2 ≤ n ≤ 100,000 where n is the length of nums and values

Example 1

Input

nums = [0, 1, 6]

values = [-5, 5, 4]

Output

14

Explanation

Here we can pick i = 1 and j = 2 to get 5 + 4 + 6 - 1

Example 2

Input

nums = [0, 3, 6]

values = [-5, 4, 8]

Output

16

Explanation

Here we can pick i = 2 and j = 2 to get 8 + 8 + 6 - 6


Solution :



title-img 




                        Solution in C++ :

int solve(vector<int>& nums, vector<int>& values) {
    int jsum = INT_MIN, isum = INT_MIN;

    for (int i = 0; i < nums.size(); i++) {
        int sum = nums[i] + values[i];
        jsum = max(jsum, sum);
        sum = values[i] - nums[i];
        isum = max(isum, sum);
    }
    return isum + jsum;
}
                    


                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums, int[] values) {
        int N = nums.length;
        int max = Integer.MIN_VALUE;
        int ans = Integer.MIN_VALUE;
        for (int j = 0; j < N; j++) {
            max = Math.max(max, values[j] - nums[j]);
            ans = Math.max(ans, nums[j] + values[j] + max);
        }
        return ans;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, values):
        ans = -1e18
        best = -1e18
        for num, value in zip(nums, values):
            best = max(best, value - num)
            ans = max(ans, num + value + best)
        return ans


View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →