Pair Sums Discussions |

7 years ago+ 0 comments

Contest is over, so I'm allowed to post code, right? Here's my partially correct solution. I would be very grateful if someone could help me with this.

#!/bin/python3

import sys

def largestValue(n, A):
    
    dp = [0, A[0] * A[1]]
    rsum = [A[0]]
    for i in range(1, n):
        rsum += [rsum[-1] + A[i]]
    for i in range(2, n):
        dp += [dp[-1] + rsum[i - 1] * A[i]]
    
    m = max(dp)
    res = m
    for i in range(n):
        # remove if-statement for O(n^2) -> passes 100% for n <= 5000
        if(dp[i] != m):
            continue
            
        rrsum = rsum[i]
        dp2 = dp[i]
        for j in range(0, i):
            rrsum -= A[j]
            dp2 -= A[j] * rrsum
            res = max(dp2, res)
        
    return res
    
if __name__ == "__main__":
    n = int(input().strip())
    A = list(map(int, input().strip().split(' ')))
    result = max(largestValue(n, A), largestValue(n, A[::-1]))
    print(result)

I find the maximum value of arrays A[0:i] for all i and just "assume" A[max_i] is an endpoint of the desired subarray. Then I just find the maximum value of arrays containing one of those endpoints.

Surprisingly, this passes for 70.4/80 points (18/21 correct). Is this because of generous test cases? Also, is A = [0,0,...,0] the only worst-case for this algorithm?

Cookie support is required to access HackerRank