I came across this problem on hacker earth contest. I was only able to think of a solution in O(n^2) time complexity. Can anyone share their approach with better time complexity.

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | sus | 176 |

6 | tourist | 176 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | -is-this-fft- | 169 |

I came across this problem on hacker earth contest. I was only able to think of a solution in O(n^2) time complexity. Can anyone share their approach with better time complexity.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/06/2021 12:46:37 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Hello !

Consider OPERATION1, we have to find the maximum sub-array sum possible including an element i. This is easy if you know Kadane's Algorithm. For each index you have to store the largest sub-array sum you can achieve. Then, find out the maximum prefix achievable from index 0 till index i-1. Your answer is going to be that (maximum prefix sum till i-1) + (maximum sub-array sum achievable including element at index i(subarray should start from index i)).

Similarly, in case OPERATION2, your answer will be (maximum suffix sum till i+1) + (maximum sub-array sum achievable including element at index i(this time the subarray should end at index i))

NONE operation is just the Kadane's Algorithm

Python 3 Code : Maximum Subarray

Can you please give the link of problem..

Actually it was from an earlier hiring challenge on hackerearth. I can't find this question in practice section now.

Why am I getting so many downvotes on this post?