leetcode

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

maximum-subarray.cpp (973B)

      1 #include <vector>
      2 #include <iostream>
      3 using namespace std;
      4 
      5 
      6 //Leet Ratings
      7 //       Speed  Memory
      8 //Total  168ms  67.6MB    
      9 //Beats  5.80%  93.55%
     10 
     11 
     12 int maxSubArray(vector<int>& nums) {
     13 
     14     int size = nums.size();
     15     int i = 0;
     16     long int current_val = 0;
     17     long int highest = nums[0];
     18     while(i < size){
     19         current_val = nums[i];
     20 
     21         //This is necessary in case the final value of a list is the highest value.
     22         if(current_val > highest){
     23             highest = current_val;
     24         }
     25         int x = i + 1;
     26         while(x < size & current_val > 0){
     27             current_val += nums[x];
     28             if(current_val > highest){
     29                 highest = current_val;
     30             }
     31             x += 1;
     32         }
     33         if(x == size){
     34             break;
     35         }
     36 
     37         i += 1;
     38         current_val = 0;
     39     }
     40     return highest;
     41 } 
     42 
     43 int main(){
     44         vector<int> vector = {10, -1, -10, 32, 3, -3};
     45         cout << maxSubArray(vector) << endl;
     46 }