Return to Answer

I'm not sure that linear time is possible for the problem as you have described it.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

Pseudocode:

int G = A_p*2 + p_max - p_min;
for(int i = 0; i < N; ++i){
    int j_start = max(i, G + i - A_p -A[i]);
    for(int j = j_start; j < N; ++j){
        int s = A[i] + A[j] + j - i;
        if( s > G){
            G = s; // You could check if you can skip ahead on J here.
        }
    }
}
return G;

I'm not sure that linear time is possible for the problem as you have described it. It is, see accepted answer.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

Pseudocode:

int G = A_p*2 + p_max - p_min;
for(int i = 0; i < N; ++i){
    int j_start = max(i, G + i - A_p -A[i]);
    for(int j = j_start; j < N; ++j){
        int s = A[i] + A[j] + j - i;
        if( s > G){
            G = s; // You could check if you can skip ahead on J here.
        }
    }
}
return G;

I'm not sure that linear time is possible for the problem as you have described it.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

I'm not sure that linear time is possible for the problem as you have described it.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

Pseudocode:

int G = A_p*2 + p_max - p_min;
for(int i = 0; i < N; ++i){
    int j_start = max(i, G + i - A_p -A[i]);
    for(int j = j_start; j < N; ++j){
        int s = A[i] + A[j] + j - i;
        if( s > G){
            G = s; // You could check if you can skip ahead on J here.
        }
    }
}
return G;

I'm not sure that linear time is possible for the problem as you have described it.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2*A_p+p_{min} + p_{max}$$.

Now you know that \$\max\limits_{i,j; i < j}A_i+A_j+(j-i) \ge G^*\$.

In order to find \$i\$, \$j\$ so that \$A_i+A_j+(j-i) > G^*\$ we want to figure out how large \$j\$ must be for us to even have a chance at getting a sum larger than \$G^*\$.

Given that \$A_i \le A_p\$ we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start a linear scan of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.

I'm not sure that linear time is possible for the problem as you have described it.

I have a way to make it faster though:

Go through the array once and find the largest value in \$A\$, label it \$A_p\$ . Make sure you keep track of the largest and smallest \$p\$ if there are duplicate values. Then let $$G^* = 2A_p+ p_{max} - p_{min}$$.

This is our greedy guess at the maximum sum that we will use as a starting point.

Next we want to find a lower bound on \$j\$ to limit our search space for any given \$i\$: $$A_i+A_j+j-i > G^* \Leftrightarrow j > G^* +i-A_i-A_j$$

Unfortunately we can't have \$A_j\$ in the calculation of the bound of \$j\$ as that wouldn't be possible to compute. But note that if we replace \$A_j\$ with \$A_p\$ which is at least as large, then we will only lower the bound on \$j\$ and we will not miss any solutions.

At this point we can start scanning of \$A\$ and update \$G^*\$ as we go to have higher and higher lower bounds on \$j\$ as we go.

Technically this is still \$O(n^2)\$ but with a smaller constant as you are able progressively take larger and larger skips.