How do I reduce Time Complexity of this solution in C++?

0
votes

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        
        int max=INT_MIN;
        int result;
        int i,j;
        if(nums.size()==1)
            return nums[0];
        if(nums.size()==0)
            return 0;
        for(i=0;i<nums.size();i++)
        {
            
            for(j=i;j<nums.size();j++)
            {
                
                result=accumulate(nums.begin()+i,nums.begin()+j+1,0);
                if(result>max)
                    max=result;
                
            }
            
        }
        return max;
    }
};

It has passed 200/202 test cases but got time limit extended issue on the rest 2 testcases.How do I optimize this?

3
c++algorithmvectordata-structuresdsa
This reads like it's from some contest/challenge/competitive coding/hacking site. Is it? If your goal is to learn C++, you won't learn anything there. In nearly all cases, like this one, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program runs slow and fails for that reason. If you're trying to learn C++, you won't learn anything from meaningless online contest sites but only from a good C++ textbook. – Sam Varshavchik
You “optimize” by employing a different algorithm. (This looks like a dynamic programming problem, so I would start there.) – molbdnilo
Yes, I figured its a dp problem, Just looking for a way i can solve it for the given time without using DP – user14001097

3 Answers

1
votes

This can be done using Kadane's Algorithm.

#include<algorithm> //this header file is required for max function.
class Solution
{
public:
    int maxSubArray(vector<int>& nums) {
        int temp=0;
        int max_sum=0;
        for(int i=0;i<nums.size();i++)
        {
            temp=max(temp+nums[i],nums[i]);
            max_sum=max(temp,max_sum);
        }
        return max_sum;
    }
};
0
votes

Below this is achieved in only one loop, from one the first googled results. With a little bookkeeping you can also hold the first and last element positions of the largest subsequence with sum max_so_far.

    #include<iostream> 
    #include<climits> 

    using namespace std; 

    int maxSubArraySum(int a[], int size) 
    { 
        int max_so_far = INT_MIN, max_ending_here = 0; 

        for (int i = 0; i < size; i++) 
        { 
            max_ending_here = max_ending_here + a[i]; 
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 

            if (max_ending_here < 0) 
                max_ending_here = 0; 
        } 
        return max_so_far; 
   }
0
votes

Have look at this link: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Couple of efficient solutions there.

Main idea is to keep a maxSum variable, that will keep track of maximum sum seen so far. You also need a currentSum variable that keeps track of sum in current window. Everytime you add a positive number to current sum,compare it to maxSum and update maxSum if currentSum > maxSum.