leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

maximum-subarrayV2.cpp (1154B)

      1 #include <vector>
      2 #include <iostream>
      3 using namespace std;
      4 
      5 
      6 //Leet Ratings
      7 //       Speed  Memory
      8 //Total  109ms  67.9MB    
      9 //Beats  84.63% 17.63%
     10 //
     11 //Optimized to start iterating once a negative is reached in the prior
     12 //set of iterations.
     13 
     14 
     15 int maxSubArray(vector<int>& nums) {
     16 
     17     int size = nums.size();
     18     int i = 0;
     19     long int current_val = 0;
     20     long int highest = nums[0];
     21     while(i < size){
     22         current_val = nums[i];
     23 
     24         //This is necessary in case the final value of a list is the highest value.
     25         if(current_val > highest){
     26             highest = current_val;
     27         }
     28         int x = i + 1;
     29         while(x < size & current_val > 0){
     30             current_val += nums[x];
     31             if(current_val > highest){
     32                 highest = current_val;
     33             }
     34             x += 1;
     35         }
     36         if(x == size){
     37             break;
     38         }
     39         if(current_val < 0){
     40             i = x;
     41         }
     42         else{
     43             i += 1;
     44         }
     45 
     46         current_val = 0;
     47     }
     48     return highest;
     49 } 
     50 
     51 int main(){
     52         vector<int> vector = {10, -1, -10, 32, 3, -3};
     53         cout << maxSubArray(vector) << endl;
     54 }