Advertisement
Guest User

Untitled

a guest
Feb 18th, 2020
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.36 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. public class Solution {
  4.     public static void main(String[] args) {
  5.         Scanner sc=new Scanner(System.in);
  6.         int t=sc.nextInt();
  7.         for(int q=0;q<t;q++){
  8.             int n=sc.nextInt();
  9.             int a[]=new int[n];
  10.             for(int i=0;i<n;i++)
  11.                 a[i]=sc.nextInt();
  12.             int ans=a[0];
  13.             int is=0,s=0,id=0;
  14.             int dp[]=new int[n];
  15.             dp[0]=a[0];
  16.             for(int i=1;i<n;i++){
  17.                 dp[i]=Math.max(0,dp[i-1])+a[i];
  18.                 ans=Math.max(ans,dp[i]);
  19.             }
  20.             // System.out.println(ans);
  21.             int max=Integer.MIN_VALUE,b=Integer.MIN_VALUE;
  22.             for(int i=0;i<n;i++){
  23.                 if(max<dp[i]){
  24.                     max=dp[i];
  25.                     id=i;
  26.                     is=s;
  27.                 }
  28.                
  29.             }
  30.            
  31.             for(int i=id;i>=0;i--){
  32.                 max=max-a[i];
  33.                 is=i;
  34.                 //System.out.println(max+" ");
  35.                 if(dp[i]==a[0]||dp[i]==0){  
  36.                    
  37.                     break;
  38.                 }
  39.             }
  40.             // for(int i=0;i<n;i++)
  41.             //     System.out.print(dp[i]+" ");
  42.             // System.out.println();
  43.             System.out.println(dp[id]+" "+is+" "+id);
  44.         }
  45.     }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement