TLE on the Divide And Conquer Approach

luG_0 · July 7, 2019, 12:25pm

This problem specifically asks for a divide and Conquer algo but gets TLE…kadane’s algo does fine although

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

This file has been truncated. show original

apaarkamal · July 7, 2019, 2:34pm

actually there is a divide and conquer approach using segment tree also …which will not give a TLE , but kadane’s algorithm is the best

luG_0 · July 8, 2019, 8:16am

why would segment tree make a difference… since there arent any updations why will it be faster then a normal divide and conquer algo?

apaarkamal · July 8, 2019, 10:13am

if the queries are of type l to r , then segment tree approach is best in use,
tell the maximum subarray sum from l to r, so we can say query(0,n-1)